Geodesic
Vertex transitive graphs G with χ_D(G) > χ(G) and small automorphism group
Ars Mathematica Contemporanea, Tome 17 (2019) no. 1, pp. 311-318.

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

For a graph G and a positive integer k, a vertex labelling f: V(G) → {1, 2, …, k} is said to be k-distinguishing if no non-trivial automorphism of G preserves the sets f − 1(i) for each i ∈ {1, …, k}. The distinguishing chromatic number of a graph G, denoted χD(G), is defined as the minimum k such that there is a k-distinguishing labelling of V(G) which is also a proper coloring of the vertices of G. In this paper, we prove the following theorem: Given k ∈ ℕ, there exists an infinite sequence of vertex-transitive graphs Gi = (Vi, Ei) such thatχD(Gi) > χ(Gi) > k,|Aut(Gi)|  2k|Vi|, where Aut(Gi) denotes the full automorphism group of Gi.In particular, this answers a question posed by the first and second authors of this paper.
DOI : 10.26493/1855-3974.1435.c71
Keywords: Distinguishing chromatic number, vertex transitive graphs, Cayley graphs 
@article{10_26493_1855_3974_1435_c71,
     author = {Niranjan Balachandran and Sajith Padinhatteeri and Pablo Spiga},
     title = {Vertex transitive graphs {G} with {\ensuremath{\chi}_D(G)} > {\ensuremath{\chi}(G)} and small automorphism group},
     journal = {Ars Mathematica Contemporanea},
     pages = {311--318},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2019},
     doi = {10.26493/1855-3974.1435.c71},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1435.c71/}
}
TY  - JOUR
AU  - Niranjan Balachandran
AU  - Sajith Padinhatteeri
AU  - Pablo Spiga
TI  - Vertex transitive graphs G with χ_D(G) > χ(G) and small automorphism group
JO  - Ars Mathematica Contemporanea
PY  - 2019
SP  - 311
EP  - 318
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1435.c71/
DO  - 10.26493/1855-3974.1435.c71
LA  - en
ID  - 10_26493_1855_3974_1435_c71
ER  - 
%0 Journal Article
%A Niranjan Balachandran
%A Sajith Padinhatteeri
%A Pablo Spiga
%T Vertex transitive graphs G with χ_D(G) > χ(G) and small automorphism group
%J Ars Mathematica Contemporanea
%D 2019
%P 311-318
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1435.c71/
%R 10.26493/1855-3974.1435.c71
%G en
%F 10_26493_1855_3974_1435_c71
Niranjan Balachandran; Sajith Padinhatteeri; Pablo Spiga. Vertex transitive graphs G with χ_D(G) > χ(G) and small automorphism group. Ars Mathematica Contemporanea, Tome 17 (2019) no. 1, pp. 311-318. doi : 10.26493/1855-3974.1435.c71. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1435.c71/

Cité par Sources :