Szczegóły publikacji
Opis bibliograficzny
A note on breaking small automorphisms in graphs / Rafał KALINOWSKI, Monika PILŚNIAK, Mariusz WOŹNIAK // Discrete Applied Mathematics ; ISSN 0166-218X. — 2017 — vol. 232, s. 221–225. — Bibliogr. s. 225, Abstr. — Publikacja dostępna online od: 2017-09-01
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 109724 |
|---|---|
| Data dodania do BaDAP | 2017-11-08 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2017.07.034 |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
This paper brings together two concepts in the theory of graph colourings: edge or total colourings distinguishing adjacent vertices and those breaking symmetries of a graph.We introduce a class of automorphisms such that edge colourings breaking them are connected to edge colouring distinguishing neighbours by multisets or sums. We call an automorphism of a graph G small if there exists a vertex of G that is mapped into its neighbour. The small distinguishing index of G, denoted Ds'(G), is the least number of colours in an edge colouring of G such that there does not exist a small automorphism of G preserving this colouring. We prove that Ds'(G)≤3 for every graph G without K2 as a component, thus supporting, in a sense, the 1-2-3 Conjecture of Karoński, Łuczak and Thomason. We also consider an analogous problem for total colourings in connection with the 1-2 Conjecture of Przybyło and Woźniak. © 2017 Elsevier B.V.