Bounds for Distinguishing Invariantsof Infinite Graphs

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Standard

Bounds for Distinguishing Invariantsof Infinite Graphs. / Imrich, Wilfried; Kalinowski, Rafal ; Skekarrizy, Mohammqad Hadi et al.
in: The journal of combinatorics, Jahrgang 24.2017, Nr. 3, 14.07.2017.

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Harvard

APA

Vancouver

Imrich W, Kalinowski R, Skekarrizy MH, Pilsniak M. Bounds for Distinguishing Invariantsof Infinite Graphs. The journal of combinatorics. 2017 Jul 14;24.2017(3). doi: 10.37236/6362

Author

Imrich, Wilfried ; Kalinowski, Rafal ; Skekarrizy, Mohammqad Hadi et al. / Bounds for Distinguishing Invariantsof Infinite Graphs. in: The journal of combinatorics. 2017 ; Jahrgang 24.2017, Nr. 3.

Bibtex - Download

@article{ce61ee37b57846908f2d73d4eb520a77,
title = "Bounds for Distinguishing Invariantsof Infinite Graphs",
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.",
author = "Wilfried Imrich and Rafal Kalinowski and Skekarrizy, {Mohammqad Hadi} and Monika Pilsniak",
year = "2017",
month = jul,
day = "14",
doi = "10.37236/6362",
language = "English",
volume = "24.2017",
journal = "The journal of combinatorics",
issn = "1097-1440",
publisher = "Electronic Journal of Combinatorics",
number = "3",

}

RIS (suitable for import to EndNote) - Download

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 -