pith. sign in

arxiv: 2605.28050 · v1 · pith:MYMZXMUKnew · submitted 2026-05-27 · 🧮 math.CO

Hadwiger's Conjecture for \{co-claw, co-gem\}-free graphs and \{fork, antifork\}-free graphs

classification 🧮 math.CO
keywords textfreegraphsco-clawco-gemforkantiforkconjecture
0
0 comments X
read the original abstract

We prove Hadwiger's Conjecture for $\{\text{co-claw}, \text{co-gem}\}$-free graphs and $\{\text{fork}, \text{antifork}\}$-free graphs, where the co-claw is the disjoint union of a triangle and a vertex, the co-gem is the disjoint union of a 4-vertex path and a vertex, the fork is obtained from $K_{1,3}$ by subdividing one of the edges, and the antifork is the complement of the fork. The $\{\text{co-claw}, \text{co-gem}\}$-free graphs include the complements of line graphs of triangle-free multigraphs, and thus our results imply Hadwiger's Conjecture for these graphs. In fact, we prove a stronger result: every $\{\text{co-claw}, \text{co-gem}\}$-free graph $G$ has a $K_{\chi(G)}$-model where each branch set has size at most 2, and every $\{\text{fork}, \text{antifork}\}$-free graph $G$ has a $K_{\chi(G)}$-model where at most one branch set has size greater than 2.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.