Bounds for Distinguishing Invariantsof Infinite Graphs
Publikationen: Beitrag in Fachzeitschrift › Artikel › Forschung › (peer-reviewed)
Autoren
Organisationseinheiten
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
Originalsprache | Englisch |
---|---|
Seitenumfang | 14 |
Fachzeitschrift | The journal of combinatorics |
Jahrgang | 24.2017 |
Ausgabenummer | 3 |
DOIs | |
Status | Veröffentlicht - 14 Juli 2017 |