Bounds for Distinguishing Invariantsof Infinite Graphs

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

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

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.
Original languageEnglish
Number of pages14
JournalThe journal of combinatorics
Volume24.2017
Issue number3
DOIs
Publication statusPublished - 14 Jul 2017

Cite this