Szczegóły publikacji
Opis bibliograficzny
Distinguishing graphs by total colourings / Rafał KALINOWSKI, Monika PILŚNIAK, Mariusz WOŹNIAK // Ars Mathematica Contemporanea ; ISSN 1855-3966. — 2016 — vol. 11 no. 1, s. 79–89. — Bibliogr. s. 89, Abstr. — Publikacja dostępna online od: 2015-09-24
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 93650 |
|---|---|
| Data dodania do BaDAP | 2015-10-20 |
| Tekst źródłowy | URL |
| DOI | 10.26493/1855-3974.751.9a8 |
| Rok publikacji | 2016 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Ars Mathematica Contemporanea |
Abstract
We introduce the total distinguishing number D ”(G) of a graph G as the least number d such that G has a total colouring (not necessarily proper) with d colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number D (G), and the distinguishing index D' (G), which are defined for colourings of vertices and edges, respectively. We obtain a general sharp upper bound: D ”(G) <= [root Delta(G)] for every connected graph G. We also introduce the total distinguishing chromatic number chi(”)(D)(G) similarly defined for proper total colourings of a graph G. We prove that chi(”)(D)(G) <= chi ”(G) + 1 for every connected graph G with the total chromatic number chi ”(G). Moreover, if chi ”(G) >= Delta(G)+ 2, then chi(”)(D)(G) = chi ”(G). We prove these results by setting sharp upper bounds for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from it.