8
$\begingroup$

I'm looking for a proof to the following statement:

Let G be a simple connected graph

If $\chi''(G)=\chi'(G)+\chi(G)$ holds then the graph should be bipartite,

where $\chi''(G)$ is the total chromatic number $\chi'(G)$ the chromatic index and $\chi(G)$ the chromatic number of a graph.

I was thinking that it should be easy so i first asked it at mathstackexchange

https://math.stackexchange.com/questions/2141570/graph-with-total-chromatic-number-chig-chig-chig

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Let $a=\chi(G)\geq 3$ and $b=\chi'(G)$. Paint the vertices in $a$ colors and edges in $b$ colors properly. Now choose one color class of edges. Repaint each of them into one of the first $a$ colors, distinct from the two colors of the edge's endpoints. Since the repainted edges were pairwise non-adjacent,we get a proper total coloring in $a+b-1$ colors.

$\endgroup$

You must log in to answer this question.

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