Geodesic
Distinguishing graphs by total colourings
Ars Mathematica Contemporanea, Tome 11 (2016) no. 1, pp. 79-89.

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

We introduce the total distinguishing number Dʺ(G) of a graph G as the least number d such that G has a total colouring (not necessarily proper) with d colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number D(G), and the distinguishing index Dʹ(G), which are defined for colourings of vertices and edges, respectively. We obtain a general sharp upper bound: Dʺ(G) ≤ ⌈√Δ (G)⌉ for every connected graph G.We also introduce the total distinguishing chromatic number χʺD(G) similarly defined for proper total colourings of a graph G. We prove that χʺD(G) ≤ χʺ(G) + 1 for every connected graph G with the total chromatic number χʺ(G). Moreover, if χʺ(G) ≥ Δ (G) + 2, then χʺD(G) = χʺ(G). We prove these results by setting sharp upper bounds for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from it.
DOI : 10.26493/1855-3974.751.9a8
Keywords: Total colourings of graphs, symmetry breaking in graphs, total distinguishing number, total distinguishing chromatic number 
@article{10_26493_1855_3974_751_9a8,
     author = {Rafa{\l} Kalinowski and Monika Pil\'sniak and Mariusz Wo\'zniak},
     title = {Distinguishing  graphs by total colourings},
     journal = {Ars Mathematica Contemporanea},
     pages = {79--89},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2016},
     doi = {10.26493/1855-3974.751.9a8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.751.9a8/}
}
TY  - JOUR
AU  - Rafał Kalinowski
AU  - Monika Pilśniak
AU  - Mariusz Woźniak
TI  - Distinguishing  graphs by total colourings
JO  - Ars Mathematica Contemporanea
PY  - 2016
SP  - 79
EP  - 89
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.751.9a8/
DO  - 10.26493/1855-3974.751.9a8
LA  - en
ID  - 10_26493_1855_3974_751_9a8
ER  - 
%0 Journal Article
%A Rafał Kalinowski
%A Monika Pilśniak
%A Mariusz Woźniak
%T Distinguishing  graphs by total colourings
%J Ars Mathematica Contemporanea
%D 2016
%P 79-89
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.751.9a8/
%R 10.26493/1855-3974.751.9a8
%G en
%F 10_26493_1855_3974_751_9a8
Rafał Kalinowski; Monika Pilśniak; Mariusz Woźniak. Distinguishing  graphs by total colourings. Ars Mathematica Contemporanea, Tome 11 (2016) no. 1, pp. 79-89. doi : 10.26493/1855-3974.751.9a8. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.751.9a8/

Cité par Sources :