PreprintarXiv licencearXiv
Every graph with no K7= minor is 6-colorable
Abstract
The first open case of Hadwiger's conjecture states that every K7-minor-free graph is 6-colorable. We prove that this is the case for K7=-minor-free graphs, where K7= denotes the graph obtained from K7 by deleting two independent edges. The proof is based on an independently interesting density result: Every 5-connected K7=-minor-free graph with n≥ 6 vertices has at most 4n−8 edges.
Related
- The ℤ-Divisor Graph on ℚ ∩ [1,7] is Planar and 3-Colorable
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- Almost Every Graph Is Reconstructible from Its Token Graphs
- Every cubic graph has four total dominating sets covering each vertex at most twice
- Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
BibTeX
@misc{dvorak2026every,
title = {{Every graph with no $K_7^=$ minor is 6-colorable}},
author = {Zdeněk Dvořák and Sergey Norin and Neil Rahman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17760},
eprint = {2609.17760},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17760},
}
RIS
TY - UNPB
TI - Every graph with no K_7^= minor is 6-colorable
AU - Zdeněk Dvořák
AU - Sergey Norin
AU - Neil Rahman
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17760
UR - https://arxiv.org/abs/2609.17760
AB - The first open case of Hadwiger's conjecture states that every K_7-minor-free graph is 6-colorable. We prove that this is the case for K_7^=-minor-free graphs, where K_7^= denotes the graph obtained from K_7 by deleting two independent edges. The proof is based on an independently interesting density result: Every 5-connected K_7^=-minor-free graph with n≥ 6 vertices has at most 4n−8 edges.
ER -