Properties of 8-contraction-critical graphs with no K₇ minor

2022/08/15 by Martin Rolek, Zi‐Xia Song, Rolek, Martin +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2208.07335

openalex publication_date 2022/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Motivated by the famous Hadwiger's Conjecture, we study the properties of 8-contraction-critical graphs with no K₇ minor; we prove that every 8-contraction-critical graph with no K₇ minor has at most one vertex of degree 8, where a graph G is 8-contraction-critical if G is not 7-colorable but every proper minor of G is 7-colorable. This is one step in our effort to prove that every graph with no K₇ minor is 7-colorable, which remains open.

Cited by

• Every graph with no K₇^\vee-minor is 6-colorable

Related

• Every graph with no K₈^-4 minor is 7-colorable
• Connectivity of contraction-critical graphs
• Graphs with no K₉^= minor are 10-colorable
• Every graph with no K₉^-6 minor is 8-colorable
• Coloring Graphs with Forbidden Minors