Journal of Combinatorics

Volume 7 (2016)

Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

Inflations of anti-cycles and Hadwiger’s Conjecture

Pages: 413 – 421

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a10

Authors

Anders Sune Pedersen (Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark)

Michael D. Plummer (Department of Mathematics, Vanderbilt University, Nashville, Tennessee, U.S.A.)

Bjarne Toft (Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark)

Abstract

Let $G$ be any graph. An inflation of a graph $G$ is obtained from $G$ first by replacing each of its vertices with either the empty set or a complete graph, and then whenever two vertices $x$ and $y$ are adjacent in $G$ we join each vertex of the replacement clique for $x$ to each vertex of the replacement clique for $y$ by an edge.

Let $G$ be any inflation of the complement of an odd cycle. It is shown that (1) $\chi(G)=\max\{\omega(G), \lceil|V(G)|/2\rceil\}$ and (2) $G\succeq K_{\chi(G)}$ by a short direct proof; that is to say, Hadwiger’s Conjecture holds for $G$. We present a comprehensive survey of the area surrounding these results.

Keywords

Hadwiger’s Conjecture, inflation, coloring, chromatic number, perfect graph, anti-cycle, quasi-line graph, vertexcritical, edge-critical

Published 23 February 2016