Contents Online

# 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

#### 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