Hadwiger's Conjecture for \{co-claw, co-gem\}-free graphs and \{fork, antifork\}-free graphs
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.