1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.