Skip to main content
added 83 characters in body
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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


          [![NodeEdgeColoring][1]][1]
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 thisI believe thisThis forces $K_4$ to have $6$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?

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


          [![NodeEdgeColoring][1]][1]
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 this forces $K_4$ to have $6$ colors.

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?

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


          [![NodeEdgeColoring][1]][1]
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?

added 83 characters in body
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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


          [![NodeEdgeColoring][1]][1]
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 this forces $K_4$ to have $6$ colors.

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?

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


          [![NodeEdgeColoring][1]][1]
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.
I believe this forces $K_4$ to have $6$ colors.

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?

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


          [![NodeEdgeColoring][1]][1]
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 this forces $K_4$ to have $6$ colors.

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?

edited tags
Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958
Loading
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958
Loading