Hadwiger's Conjecture with Certain Forbidden Induced Subgraphs

arXiv2211.00259MaRDI QIDQ6415744

Daniel Carter

Publication date: 31 October 2022

Abstract: We prove that $overline{K}_3,H$-free graphs are not counterexamples to Hadwiger's Conjecture, where $H$ is any one of 33 graphs on seven, eight, or nine vertices, or $H=K_8$. This improves on past results of Plummer-Stiebitz-Toft, Kriesell, and Bosse. The proofs are mostly computer-assisted.

Has companion code repository: https://github.com/dcartermath/hc-forbidden-subgraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

This page was built for publication: Hadwiger's Conjecture with Certain Forbidden Induced Subgraphs

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