Skip to main content
Bumped by Community user
added 1 character in body
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

As aan outgrowth of this question, I have another question, that is, why not the definition of conformability includes a $\Delta$ vertex coloring also, instead of only $\Delta+1$ coloring of vertices. This is because, the square of the $8$ cycle, $C_8^2$ is easily seen to have a $\Delta$ conformable coloring(each color class has only two vertices), whereas I do not see a $\Delta+1$ conformable coloring( the number of vertices in each color class cannot exceed two, hence, a five coloring should have one vertex in at least two color classes). But, the graph is Type 1( total colorable with $\Delta+1$ colors) Am I missing something here? Thanks beforehand.

As a outgrowth of this question, I have another question, that is, why not the definition of conformability includes a $\Delta$ vertex coloring also, instead of only $\Delta+1$ coloring of vertices. This is because, the square of the $8$ cycle, $C_8^2$ is easily seen to have a $\Delta$ conformable coloring(each color class has only two vertices), whereas I do not see a $\Delta+1$ conformable coloring( the number of vertices in each color class cannot exceed two, hence, a five coloring should have one vertex in at least two color classes). But, the graph is Type 1( total colorable with $\Delta+1$ colors) Am I missing something here? Thanks beforehand.

As an outgrowth of this question, I have another question, that is, why not the definition of conformability includes a $\Delta$ vertex coloring also, instead of only $\Delta+1$ coloring of vertices. This is because, the square of the $8$ cycle, $C_8^2$ is easily seen to have a $\Delta$ conformable coloring(each color class has only two vertices), whereas I do not see a $\Delta+1$ conformable coloring( the number of vertices in each color class cannot exceed two, hence, a five coloring should have one vertex in at least two color classes). But, the graph is Type 1( total colorable with $\Delta+1$ colors) Am I missing something here? Thanks beforehand.

Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Clarifications regarding conformability in graph colorings

As a outgrowth of this question, I have another question, that is, why not the definition of conformability includes a $\Delta$ vertex coloring also, instead of only $\Delta+1$ coloring of vertices. This is because, the square of the $8$ cycle, $C_8^2$ is easily seen to have a $\Delta$ conformable coloring(each color class has only two vertices), whereas I do not see a $\Delta+1$ conformable coloring( the number of vertices in each color class cannot exceed two, hence, a five coloring should have one vertex in at least two color classes). But, the graph is Type 1( total colorable with $\Delta+1$ colors) Am I missing something here? Thanks beforehand.