Bounds for Distinguishing Invariantsof Infinite Graphs

Wilfried Imrich, Rafal Kalinowski, Mohammqad Hadi Skekarrizy, Monika Pilsniak

Publikation: Beitrag in FachzeitschriftArtikelForschungBegutachtung

5 Zitate (Scopus)


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.
FachzeitschriftThe journal of combinatorics
PublikationsstatusVeröffentlicht - 14 Juli 2017

Dieses zitieren