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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There is nothing to be missed. In fact, a $\Delta$-conformable(or any $k$-conformable coloring, where $k\le\Delta+1$) induces a $\Delta+1$-conformable coloring in case of even order graphs, as one(or more) color class(es) can be taken to have $0$ vertices, which has same parity as the total number of vertices. However, this might not be true for odd order graphs. In this case, the square of $8$-cycle is a graph of even order.