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?

  • 6
    $\begingroup$ Perhaps a total coloring is what you seek? $\endgroup$ Nov 14, 2015 at 4:20
  • $\begingroup$ Take 1234 cycle, diagonals 13,24 have color 5, sides 12,23,34,41 have colors 3,4,1,2 $\endgroup$ Nov 14, 2015 at 6:51

1 Answer 1


This is known as a total coloring. It has not received a huge amount of attention in the literature, though this masters thesis seems a good place to start.

  • 4
    $\begingroup$ 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. $\endgroup$ Nov 14, 2015 at 11:33
  • $\begingroup$ Is this number known for $K_n$ ( complete graph )? Gerhard "Feeling Somewhat Colorful This Day" Paseman, 2015.11.14 $\endgroup$ Nov 14, 2015 at 16:16
  • 2
    $\begingroup$ For the complete graph $K_n$, the total chromatic number is $n$ or $n+1$ for odd and even $n$ respectively. $\endgroup$ Nov 15, 2015 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.