3
$\begingroup$

There must be work on this concept, but I am not finding it through searches, perhaps using the wrong terminology.

          NodeEdgeColoring
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?

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ Perhaps a total coloring is what you seek? $\endgroup$
    – Gordon Royle
    Commented 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$
    – Fedor Petrov
    Commented Nov 14, 2015 at 6:51

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Gordon Royle
    Commented Nov 15, 2015 at 11:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .