# Node-edge coloring of graphs

There must be work on this concept, but I am not finding it through searches, perhaps using the wrong terminology. Define a node-edge coloring of a graph $G=(V,E)$ to assign an integer color to each node and edge of $G$, such that

1. No two adjacent nodes are assigned the same color.
2. No two edges incident to the same node have the same color.
3. No edge incident to a node has the same color as that node. Or, equivalently, a node's color is distinct from all its incident edges colors.

I believe thisThis forces $K_4$ to have 6 $5$ colors (Thanks to Fedor Petrov for the coloring.)

Q. Has this type of coloring been studied? Does it have a name in the literature? Or is it instead just a combination of $G$ and the line graph of $G$ and so not worthy of separate study?

• Perhaps a total coloring is what you seek? – Gordon Royle Nov 14 '15 at 4:20
• Take 1234 cycle, diagonals 13,24 have color 5, sides 12,23,34,41 have colors 3,4,1,2 – Fedor Petrov Nov 14 '15 at 6:51

• Actually it has received some interest. The total coloring conjecture is that the total chromatic number is at most $\Delta + 2$ (maximum degree plus 2). This was conjectured by the Iranian mathematician Mehdi Behzad in the 1960s, but also appeared in the work of Vizing (note the similarity to Vizing's edge chromatic number theorem), and who has priority is in some dispute. – Gordon Royle Nov 14 '15 at 11:33
• Is this number known for $K_n$ ( complete graph )? Gerhard "Feeling Somewhat Colorful This Day" Paseman, 2015.11.14 – Gerhard Paseman Nov 14 '15 at 16:16
• For the complete graph $K_n$, the total chromatic number is $n$ or $n+1$ for odd and even $n$ respectively. – Gordon Royle Nov 15 '15 at 11:53