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 -