Geodesic
The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 165-174.

Voir la notice de l'article provenant de la source Library of Science

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, . . ., k. A list assignment to G is an assignment L = L(v)v∈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 ∈ 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.
Keywords: distinguishing, distinguishing number, list distinguishing, interval graph 
@article{DMGT_2017_37_1_a12,
     author = {Immel, Poppy and Wenger, Paul S.},
     title = {The list {Distinguishing} {Number} {Equals} the {Distinguishing} {Number} for {Interval} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {165--174},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a12/}
}
TY  - JOUR
AU  - Immel, Poppy
AU  - Wenger, Paul S.
TI  - The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 165
EP  - 174
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a12/
LA  - en
ID  - DMGT_2017_37_1_a12
ER  - 
%0 Journal Article
%A Immel, Poppy
%A Wenger, Paul S.
%T The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 165-174
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a12/
%G en
%F DMGT_2017_37_1_a12
Immel, Poppy; Wenger, Paul S. The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 165-174. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a12/

[1] M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) #N17.

[2] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) #R18.

[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

[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

[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

[7] C.T. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin. 13 (2006) #R11.

[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

[9] P. Erdős, A. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1980) 125–157.

[10] M. Ferrara, B. Flesch and E. Gethner, List-distinguishing colorings of graphs, Electron. J. Combin. 18 (2011) #P161.

[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

[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].

[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

[14] D. Fulkerson and O. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835–855.

[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

[16] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250–260. doi:10.1002/jgt.20190

[17] W. Imrich, S. Klavžar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007) #R36.

[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

[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

[20] A. Lombardi, Distinguishing extension numbers for ℝn and Sn, 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

[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).