Distant set distinguishing total colourings of graphs

Jakub Przybyło¹

¹AGH University of Science and Technology, al. A. Mickiewicza 30, 30-059 Krakow, Poland

The electronic journal of combinatorics, Tome 23 (2016) no. 2

Résumé

The Total Colouring Conjecture suggests that $\Delta+3$ colours ought to suffice in order to provide a proper total colouring of every graph $G$ with maximum degree $\Delta$. 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 $G$ 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 $\Delta+C$, for a constant $C>0$ still remains valid even after extending the distinction requirement to pallets associated with vertices at distance at most $r$, if only $G$ has minimum degree $\delta$ larger than a constant dependent on $r$. We prove that such assumption on $\delta$ 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))\Delta$ for every $r$, and show that for any fixed $\epsilon\in(0,1]$ and $r$, the conjecture holds if $\delta\geq \varepsilon\Delta$, i.e., in particular for regular graphs.

Détail

DOI : 10.37236/5481

Classification : 05C15
Mots-clés : Zhang's conjecture, adjacent vertex distinguishing total chromatic number, total neighbour distinguishing index, \(d\)-strong total chromatic number, \(r\)-adjacent strong total chromatic number, \(r\)-distant set distinguishing total number