کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649578 | 1342460 | 2009 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results](/preview/png/4649578.png)
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.
Journal: Discrete Mathematics - Volume 309, Issue 16, 28 August 2009, Pages 5169–5182