Szczegóły publikacji
Opis bibliograficzny
Distant set distinguishing total colourings of graphs / Jakub PRZYBYŁO // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2016 — vol. 23 iss. 2, s. 1–20, art. no. P2.54. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 19–20, Abstr. — Publikacja dostępna online od: 2016-06-24
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 102537 |
|---|---|
| Data dodania do BaDAP | 2016-12-16 |
| Tekst źródłowy | URL |
| Rok publikacji | 2016 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | The Electronic Journal of Combinatorics |
Abstract
The Total Colouring Conjecture suggests that Δ+3Δ+3 colours ought to suffice in order to provide a proper total colouring of every graph GG with maximum degree ΔΔ. Thus far this has been confirmed up to an additive constant factor, and the same holds even if one additionally requires every pair of neighbours in GG to differ with respect to the sets of their incident colours, so called pallets. Within this paper we conjecture that an upper bound of the form Δ+CΔ+C, for a constant C>0C>0 still remains valid even after extending the distinction requirement to pallets associated with vertices at distance at most rr, if only GG has minimum degree δδ larger than a constant dependent on rr. We prove that such assumption on δδ is then unavoidable and exploit the probabilistic method in order to provide two supporting results for the conjecture. Namely, we prove the upper bound (1+o(1))Δ(1+o(1))Δ for every rr, and show that for any fixed ϵ∈(0,1]ϵ∈(0,1] and rr, the conjecture holds if δ≥εΔδ≥εΔ, i.e., in particular for regular graphs.