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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .