Bounds for Distinguishing Invariantsof Infinite Graphs

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Autoren

Externe Organisationseinheiten

  • Berg- und Hüttenakademie Krakau
  • Firdausi-Universität Maschhad

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.

Details

OriginalspracheEnglisch
Seitenumfang14
FachzeitschriftThe journal of combinatorics
Jahrgang24.2017
Ausgabenummer3
DOIs
StatusVeröffentlicht - 14 Juli 2017