Back to Search
Start Over
The Hilton--Zhao Conjecture is True for Graphs with Maximum Degree 4
- Source :
- SIAM Journal on Discrete Math. 33(3), 2019, pp. 1228-1241
- Publication Year :
- 2017
-
Abstract
- A simple graph $G$ is \emph{overfull} if $|E(G)|>\Delta\lfloor|V(G)|/2\rfloor$. By the pigeonhole principle, every overfull graph $G$ has $\chi'(G)>\Delta$. The \emph{core} of a graph, denoted $G_\Delta$, is the subgraph induced by its vertices of degree $\Delta$. Vizing's Adjacency Lemma implies that if $\chi'(G)>\Delta$, then $G_\Delta$ contains cycles. Hilton and Zhao conjectured that if $G_\Delta$ has maximum degree 2 and $\Delta\ge 4$, then $\chi'(G)>\Delta$ precisely when $G$ is overfull. We prove this conjecture for the case $\Delta=4$.<br />Comment: 13 pages, 9 figures; this version incorporates reviewer feedback and corrects a few errors; to appear in SIAM J. Discrete Math
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Journal :
- SIAM Journal on Discrete Math. 33(3), 2019, pp. 1228-1241
- Publication Type :
- Report
- Accession number :
- edsarx.1703.00959
- Document Type :
- Working Paper