# zbMATH — the first resource for mathematics

The relationship between an edge colouring conjecture and a total colouring conjecture. (English) Zbl 0741.05030
Let $$G=(V(G),E(G))$$ denote a simple graph with maximum degree $$\Delta(G)$$, minimum degree $$\delta(G)$$ and $$\hbox{def}(G)=\sum_{v\in V(G)}(\Delta(G)-d_ G(v))$$. The chromatic index $$\chi'(G)$$ of $$G$$ is the least value of $$| C|$$ for which $$G$$ has a proper edge colouring with colour set $$C$$. Note that $$\Delta(G)\leq\chi'(G)\leq\Delta(G)+1$$. There are an edge-colouring conjecture $$(*)$$ and a total-colouring conjecture $$(**)$$ by Chetwynd and Hilton: $$(*)$$ If $$G$$ satisfies $$\Delta(G)>{1\over 3}| V(G)|$$, then $$\chi'(G)=\Delta(G)+1$$ iff $$G$$ contains a subgraph $$H=(V(H),E(H))$$ with $$| E(H)|>\Delta(H)\lfloor{1\over 2}| V(H)|\rfloor$$ and $$\Delta(G)=\Delta(H)$$. $$(**)$$ If $$G$$ satisfies $$\Delta(G)\geq{1\over 2}(| V(G)|+1)$$, then $$\chi'(G)=\Delta(G)+1$$ iff $$G$$ contains a non-conformable subgraph $$H$$ with $$\Delta(H)=\Delta(G)$$. The authors show that if $$(*)$$ is true for graphs of even order satisfying $$\Delta(G)>{1\over 2}| V(G)|$$, then $$(**)$$ is true for graphs of odd order satisfying $$\delta(G)\geq{3\over 4}| V(G)|-{1\over 4}$$ and $$\hbox{def}(G)\geq 2(\Delta(G)-\delta(G)+1)$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs