Hadwiger's Conjecture with Certain Forbidden Induced Subgraphs

MaRDI QIDQ6415744zbMATH OpenFDO

Authors Daniel Carter

Publication date 31 October 2022

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

Mathematics Subject Classification ID

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

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.

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)