The overfull conjecture and the conformability conjecture (Q5951946)

Vizing's well-known result that \(\triangle (G) \leq \chi '(G) \leq \triangle (G) +1\) (where \(\chi '\) denotes the chromatic index) led to the classification of a graph as Class 1 if \(\chi '(G) =\triangle (G)\) and Class 2 if \(\chi '(G) =\triangle (G) +1\). The overfull conjecture of \textit{A. G. Chetwynd} and \textit{A. J. W. Hilton} [Star multigraphs with three vertices of maximum degree, Math. Proc. Camb. Philos. Soc. 100, 303-317 (1986)] is Conjecture 1: If \(G\) is a graph satisfying \(\triangle (G)>\frac{1}{3}|V(G)|,\) then \(G\) is of Class 2 if and only if \(G\) contains a subgraph \(H\) with \(\triangle (H)=\triangle(G)\) and \(|E(H) |>\triangle (H)\lfloor \frac{V(H)}{2}\rfloor .\) The total chromatic number conjecture is that \(\triangle (G) +1\leq \chi _{T}(G) \leq \triangle (G) +2,\) where \(\chi _{T}(G) \) denotes the total chromatic number. If \(\chi _{T}(G) =\triangle (G) +1\) then \(G\) is called Type 1, and if \(\chi _{T}(G) =\triangle (G) +2,\) then \(G\) is called Type 2. A graph \(G\) is conformable if it has a vertex colouring in \(\triangle (G) +1\) colours such that the number of colour classes with parity different from that of \(|V(G)|\) is less than or equal to the deficiency \(\sum_{v\in V(G)}(\triangle (G)-d_{G}(v))\). The modified conformability conjecture [\textit{G. M. Hamilton, A. J. W. Hilton} and \textit{H. R. F. Hind}, CRM Proc. Lect. Notes 23, 43-98 (1999; Zbl 0943.05034)] is Conjecture 2: If \(G\) is a graph satisfying \(\triangle (G)\geq \frac{1}{2}(|V(G) |+1) ,\) then \(G\) is Type 2 if and only if \(G\) contains a subgraph \(H\) with \(\triangle (H) =\triangle (G) \) which is either non-conformable, or, when \(\triangle (G) \) is even, consists of \(K_{\triangle (G) +1},\) with one edge subdivided. In this paper it is shown that under some fairly general conditions Conjecture 1 implies Conjecture 2. It is also shown that if \(G\) has even order and high maximum degree, then \(G\) is conformable unless the deficiency is very small.