Szczegóły publikacji
Opis bibliograficzny
Bounds for distinguishing invariants of infinite graphs / Wilfried Imrich, Rafał KALINOWSKI, Monika PILŚNIAK, Mohammad Hadi Shekarriz // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2017 — vol. 24 iss. 3, art. no. P3.6, s. 1–14. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 13–14, Abstr. — Publikacja dostępna online od: 2017-07-14
Autorzy (4)
- Imrich Wilfried
- AGHKalinowski Rafał
- AGHPilśniak Monika
- Shekarriz Mohammad Hadi
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 107393 |
|---|---|
| Data dodania do BaDAP | 2017-07-17 |
| Tekst źródłowy | URL |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | The Electronic Journal of Combinatorics |
Abstract
We consider infinite graphs. The distinguishing number D(G) of a graph G is the minimum number of colours in a vertex colouring of G that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by D′(G). We prove that D′(G)≤D(G)+1. For proper colourings, we study relevant invariants called the distinguishing chromatic number χD(G), and the distinguishing chromatic index χ′D(G), for vertex and edge colourings, respectively. We show that χD(G)≤2Δ(G)−1 for graphs with a finite maximum degree Δ(G), and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that χ′D(G)≤χ′(G)+1, where χ′(G) is the chromatic index of G, and we prove a similar result χ′′D(G)≤χ′′(G)+1 for proper total colourings. A number of conjectures are formulated.
