On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results

A vertex kk-coloring   of graph GG is distinguishing   if the only automorphism of GG that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number of  GG, D(G)D(G), is the smallest integer kk so that GG has a distinguishing kk-coloring; the distinguishing chromatic number of  GG, χD(G)χD(G), is defined similarly.It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter–the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and   the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n3log3n)O(n3log3n) time for graphs with nn vertices. We also prove a number of results regarding the computational complexity of determining a graph’s distinguishing chromatic number.