Bounds for Distinguishing Invariantsof Infinite Graphs
Research output: Contribution to journal › Article › Research › peer-review
Standard
In: The journal of combinatorics, Vol. 24.2017, No. 3, 14.07.2017.
Research output: Contribution to journal › Article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex - Download
}
RIS (suitable for import to EndNote) - Download
TY - JOUR
T1 - Bounds for Distinguishing Invariantsof Infinite Graphs
AU - Imrich, Wilfried
AU - Kalinowski, Rafal
AU - Skekarrizy, Mohammqad Hadi
AU - Pilsniak, Monika
PY - 2017/7/14
Y1 - 2017/7/14
N2 - We consider infinite graphs. The distinguishing numberD(G) of a graphGisthe minimum number of colours in a vertex colouring ofGthat is preserved onlyby the trivial automorphism. An analogous invariant for edge colourings is calledthe distinguishing index, denoted byD′(G). We prove thatD′(G)6D(G) + 1. Forproper colourings, we study relevant invariants called the distinguishing chromaticnumberχD(G), and the distinguishing chromatic indexχ′D(G), for vertex and edgecolourings, respectively. We show thatχD(G)62∆(G)−1 for graphs with a finitemaximum degree ∆(G), and we obtain substantially lower bounds for some classesof graphs with infinite motion. We also show thatχ′D(G)6χ′(G) + 1, whereχ′(G)is the chromatic index ofG, and we prove a similar resultχ′′D(G)6χ′′(G) + 1 forproper total colourings. A number of conjectures are formulated.
AB - We consider infinite graphs. The distinguishing numberD(G) of a graphGisthe minimum number of colours in a vertex colouring ofGthat is preserved onlyby the trivial automorphism. An analogous invariant for edge colourings is calledthe distinguishing index, denoted byD′(G). We prove thatD′(G)6D(G) + 1. Forproper colourings, we study relevant invariants called the distinguishing chromaticnumberχD(G), and the distinguishing chromatic indexχ′D(G), for vertex and edgecolourings, respectively. We show thatχD(G)62∆(G)−1 for graphs with a finitemaximum degree ∆(G), and we obtain substantially lower bounds for some classesof graphs with infinite motion. We also show thatχ′D(G)6χ′(G) + 1, whereχ′(G)is the chromatic index ofG, and we prove a similar resultχ′′D(G)6χ′′(G) + 1 forproper total colourings. A number of conjectures are formulated.
U2 - 10.37236/6362
DO - 10.37236/6362
M3 - Article
VL - 24.2017
JO - The journal of combinatorics
JF - The journal of combinatorics
SN - 1097-1440
IS - 3
ER -
