The adjacent vertex distinguishing total chromatic number
Authors:
Preprint
Abstract
A well-studied concept is that of the total chromatic number. A proper total colouring of a graph is a colouring of both vertices and edges so that every pair of adjacent vertices receive different colours, every pair of adjacent edges receive different colours and every vertex and incident edge receive different colours. This paper considers a strengthening of this condition and examines the minimum number of colours required for a total colouring with the additional property that for any adjacent vertices $u$ and $v$, the sets of colours incident to $u$ is different from the set of colours incident to $v$. It is shown that there is a constant $C$ so that for any graph $G$, there exists such a colouring using at most $\Delta(G) + C$ colours.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Concise proofs for adjacent vertex-distinguishing total coloringsDiscrete Mathematics, 2009
- On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3Journal of Combinatorial Optimization, 2007
- Adjacent Vertex Distinguishing Edge‐ColoringsSIAM Journal on Discrete Mathematics, 2007
- Concentration for self‐bounding functions and an inequality of TalagrandRandom Structures & Algorithms, 2006
- Adjacent strong edge coloring of graphsApplied Mathematics Letters, 2002
- A Bound on the Total Chromatic NumberCombinatorica, 1998
- Vertex-distinguishing proper edge-coloringsJournal of Graph Theory, 1997
- New concentration inequalities in product spacesInventiones Mathematicae, 1996
- Concentration of measure and isoperimetric inequalities in product spacesPublications mathématiques de l'IHÉS, 1995
- SOME UNSOLVED PROBLEMS IN GRAPH THEORYRussian Mathematical Surveys, 1968