×

The list distinguishing number equals the distinguishing number for interval graphs. (English) Zbl 1354.05086

Summary: A distinguishing coloring of a graph \(G\) is a coloring of the vertices so that every nontrivial automorphism of \(G\) maps some vertex to a vertex with a different color. The distinguishing number of \(G\) is the minimum \(k\) such that \(G\) has a distinguishing coloring where each vertex is assigned a color from \(\{1, \dots, k\}\). A list assignment to \(G\) is an assignment \(L = \{L(v)\}_{v\in V(G)}\) of lists of colors to the vertices of \(G\). A distinguishing \(L\)-coloring of \(G\) is a distinguishing coloring of \(G\) where the color of each vertex \(v\) comes from \(L(v)\). The list distinguishing number of \(G\) is the minimum \(k\) such that every list assignment to \(G\) in which \(|L(v)| = k\) for all \(v\in V(G)\) yields a distinguishing \(L\)-coloring of \(G\). We prove that if \(G\) is an interval graph, then its distinguishing number and list distinguishing number are equal.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) #N17.; · Zbl 1082.05047
[2] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) #R18.; · Zbl 0851.05088
[3] V. Arvind, C. Cheng and N. Devanur, On computing the distinguishing numbers of planar graphs and beyond: a counting approach, SIAM J. Discrete Math. 22 (2008) 1297-1324. doi:10.1137/07068686X; · Zbl 1226.05210
[4] V. Arvind and N. Devanur, Symmetry breaking in trees and planar graphs by vertex coloring, in: Proceedings of the 8th Nordic Combinatorial Conference, Aalborg University (Aalborg, Denmark, 2004).;
[5] K. Booth and G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci. 13 (1976) 335-379. doi:10.1016/S0022-0000(76)80045-1; · Zbl 0367.68034
[6] C.T. Cheng, On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results, Discrete Math. 309 (2009) 5169-5182. doi:10.1016/j.disc.2009.04.004; · Zbl 1213.05071
[7] C.T. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin. 13 (2006) #R11.; · Zbl 1080.05081
[8] C. Colbourn and K. Booth, Linear time automorphism algorithms for trees, interval graphs, and planar graphs, SIAM J. Comput. 10 (1981) 203-225. doi:10.1137/0210015; · Zbl 0456.05024
[9] P. Erdős, A. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1980) 125-157.; · Zbl 0469.05032
[10] M. Ferrara, B. Flesch and E. Gethner, List-distinguishing colorings of graphs, Electron. J. Combin. 18 (2011) #P161.; · Zbl 1230.05127
[11] M. Ferrara, E. Gethner, S.G. Hartke, D. Stolee and P.S. Wenger, List distinguishing parameters of trees, Discrete Appl. Math. 161 (2013) 864-869. doi:10.1016/j.dam.2012.10.003; · Zbl 1262.05050
[12] M. Ferrara, E. Gethner, S.G. Hartke, D. Stolee and P.S. Wenger, Extending precolorings to distinguish group actions, arXiv:1405.5558 [math.CO].; · Zbl 1390.05065
[13] M. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs, Discrete Math. 308 (2008) 2240-2246. doi:10.1016/j.disc.2007.04.070; · Zbl 1147.05029
[14] D. Fulkerson and O. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835-855.; · Zbl 0132.21001
[15] W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian products of complete graphs, European J. Combin. 29 (2008) 922-929. doi:10.1016/j.ejc.2007.11.018; · Zbl 1205.05198
[16] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250-260. doi:10.1002/jgt.20190; · Zbl 1108.05080
[17] W. Imrich, S. Klavžar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007) #R36.; · Zbl 1124.05044
[18] S. Klavžar, T.-L. Wong and X. Zhu, Distinguishing labellings of group action on vector spaces and graphs, J. Algebra 303 (2006) 626-641. doi:10.1016/j.jalgebra.2006.01.045; · Zbl 1105.05031
[19] S. Klavžar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, European J. Combin. 28 (2007) 303-310. doi:10.1016/j.ejc.2005.07.001; · Zbl 1105.05032
[20] A. Lombardi, Distinguishing extension numbers for \(ℝ^n\) and \(S^n\), arXiv:1408.5849 [math.co] (2014).;
[21] G. Lueker and K. Booth, A linear time algorithm for deciding interval graph isomorphism, J. Assoc. Comput. Mach. 26 (1979) 183-195. doi:10.1145/322123.322125; · Zbl 0402.68050
[22] V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz, Metody Diskret. Anal. v Teorii Kodov i Shem 29 (1976) 3-10 (in Russian).; · Zbl 0362.05060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.