Distant set distinguishing total colourings of graphs

Abstract

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 +const.$ 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 the conjecture holds if $\delta \ge \epsilon \Delta$ for any fixed $\epsilon \in (0,1]$ and $r$, i.e., in particular for regular graphs.

arXiv comment18 pages. arXiv admin note: text overlap with arXiv:1508.05024