Geodesic
χ_D(G), |Aut(G)|, and a variant of the Motion Lemma
Ars Mathematica Contemporanea, Tome 12 (2017) no. 1, pp. 89-109.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

The Distinguishing Chromatic Number of a graph G, denoted χD(G), was first defined in K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16, as the minimum number of colors needed to properly color G such that no non-trivial automorphism ϕ of the graph G fixes each color class of G. In this paper,We prove a lemma that may be considered a variant of the Motion lemma of A. Russell and R. Sundaram, A note on the asympotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), #R23, and use this to give examples of several families of graphs which satisfy χD(G) = χ(G) + 1.We give an example of families of graphs that admit large automorphism groups in which every proper coloring is distinguishing. We also describe families of graphs with (relatively) very small automorphism groups which satisfy χD(G) = χ(G) + 1, for arbitrarily large values of χ(G).We describe non-trivial families of bipartite graphs that satisfy χD(G) > r for any positive integer r.
DOI : 10.26493/1855-3974.848.669
Keywords: Distinguishing chromatic number, automorphism group of a graph, Motion Lemma, weak product of graphs 
@article{10_26493_1855_3974_848_669,
     author = {Niranjan Balachandran and Sajith Padinhatteeri},
     title = {\ensuremath{\chi}_D(G), {|Aut(G)|,} and a variant of the {Motion} {Lemma}},
     journal = {Ars Mathematica Contemporanea},
     pages = {89--109},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2017},
     doi = {10.26493/1855-3974.848.669},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.848.669/}
}
TY  - JOUR
AU  - Niranjan Balachandran
AU  - Sajith Padinhatteeri
TI  - χ_D(G), |Aut(G)|, and a variant of the Motion Lemma
JO  - Ars Mathematica Contemporanea
PY  - 2017
SP  - 89
EP  - 109
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.848.669/
DO  - 10.26493/1855-3974.848.669
LA  - en
ID  - 10_26493_1855_3974_848_669
ER  - 
%0 Journal Article
%A Niranjan Balachandran
%A Sajith Padinhatteeri
%T χ_D(G), |Aut(G)|, and a variant of the Motion Lemma
%J Ars Mathematica Contemporanea
%D 2017
%P 89-109
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.848.669/
%R 10.26493/1855-3974.848.669
%G en
%F 10_26493_1855_3974_848_669
Niranjan Balachandran; Sajith Padinhatteeri. χ_D(G), |Aut(G)|, and a variant of the Motion Lemma. Ars Mathematica Contemporanea, Tome 12 (2017) no. 1, pp. 89-109. doi : 10.26493/1855-3974.848.669. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.848.669/

Cité par Sources :