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

05C15 Coloring of graphs and hypergraphs