Distant set distinguishing total colourings of graphs (Q2629496)

Summary: 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 \epsilon\Delta\), i.e., in particular for regular graphs.