1
$\begingroup$

What can we say about the total chromatic number of regular bipartite graphs that are not complete? Can we say they are of type 1[Total Colorable(no adjacent/incident elements have same color) by $\Delta+1$ colors where $\Delta$ is the maximum degree of the graph].

Can we say that regular, noncomplete bipartite graphs are formed by removing 1-factors recursively? If that be the case, then I think these graphs are of type 1. Any hints? Thanks beforehand.

On the other hand, can we use adjacent strong edge coloring, as mentioned here

$\endgroup$
1
$\begingroup$

No, any even cycle graph with order not divisible by $3$ is a regular bipartite graph with total chromatic number $4=\Delta+2\,\,,\Delta=2$. Therefore, it may be conjectured that a regular bipartite graph with every cycle(or posibly girth) divisible by $3$ would satisfy being type $1$.

$\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.