The overfull conjecture and the conformability conjecture

DOI10.1016/S0012-365X(01)00153-4MaRDI QIDQ5951946zbMATH OpenOpenAlexWikidataFDO

Authors A. J. W. Hilton, Fred C. Holroyd, Cheng Zhao

Publication date 28 August 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00153-4

zbMATH Keywords

conformability conjectureedge colouringoverfull conjecturetotal colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• Two conjectures on edge-colouring
• scientific article; zbMATH DE number 1463391
• Non-conformable subgraphs of non-conformable graphs
• A note on total chromatic numbers of graphs
• Recent progress on edge-colouring graphs

Cited in

(13)

• Recent progress on edge-colouring graphs
• Two conjectures on edge-colouring
• Non-conformable subgraphs of non-conformable graphs
• The Hall-condition index of a graph and the overfull conjecture
• scientific article; zbMATH DE number 1146230 (Why is no real title available?)
• scientific article; zbMATH DE number 1998290 (Why is no real title available?)
• scientific article; zbMATH DE number 1463391 (Why is no real title available?)
• A note on total chromatic numbers of graphs
• scientific article; zbMATH DE number 1390130 (Why is no real title available?)
• The overfull conjecture on split-comparability and split-interval graphs
• Results about the total chromatic number and the conformability of some families of circulant graphs
• On the conformability of regular line graphs
• Graph factors and factorization: 1985--2003: a survey

This page was built for publication: The overfull conjecture and the conformability conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951946)