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$ – Gordon Royle Nov 14 '15 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$ – Fedor Petrov Nov 14 '15 at 6:51

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$ – Gordon Royle Nov 14 '15 at 11:33
  • $\begingroup$ Is this number known for $K_n$ ( complete graph )? Gerhard "Feeling Somewhat Colorful This Day" Paseman, 2015.11.14 $\endgroup$ – Gerhard Paseman Nov 14 '15 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$ – Gordon Royle Nov 15 '15 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.