The perfect divisibility and chromatic number of some odd hole-free graphs

This paper establishes that (odd hole, hammer, $K_{2,3}$)-free graphs are perfectly divisible and provides specific polynomial and linear bounds on the chromatic number for various classes of short-holed graphs.

The Gist

Imagine you are the mayor of a very strange city called Graphville. In this city, the buildings are vertices (dots), and the roads connecting them are edges (lines). Your job is to assign a color (like a paint color) to every building.

There is one strict rule: No two buildings connected by a road can have the same color.

Your goal is to use as few colors as possible. The minimum number of colors you need is called the Chromatic Number ($\chi$).

However, there's a catch. Some buildings form tight little circles called Cliques (where everyone knows everyone). If you have a clique of 5 buildings, you must use 5 different colors just for that group. The size of the largest clique in your city is called the Clique Number ($\omega$).

Usually, the number of colors you need ($\chi$) is close to the size of your biggest clique ($\omega$). But in some chaotic cities, you might have a small clique (say, 3 buildings) but need 100 colors to paint the whole city because of weird, twisted road patterns.

The "Odd Hole" Problem

In Graphville, a Hole is a circular road that goes around without any shortcuts (diagonal roads) cutting through it.

• An Odd Hole is a circle with an odd number of buildings (5, 7, 9, etc.).

Mathematicians have known for a long time that if a city has no Odd Holes, it's usually easier to paint. But even then, it's incredibly hard to figure out the exact number of colors needed. It's like trying to solve a maze that changes shape every time you look at it.

This paper is about three specific types of Graphville cities that the authors, Weihua He and his team, managed to "tame." They proved that for these specific cities, the number of colors needed is predictable and manageable.

---

The Three Special Cities

The authors studied three specific types of "forbidden" shapes. If a city doesn't have these shapes, it behaves nicely.

1. The "Hammer" and "K2,3" Free City

The Analogy: Imagine a city where you can't build a Hammer (a triangle with a stick attached) or a specific Spiderweb shape (called $K_{2,3}$).

• The Result: The authors proved that these cities are "Perfectly Divisible."
• What does that mean? Think of the city as a giant cake. "Perfectly Divisible" means you can slice the cake into two pieces:
  1. Piece A: A "Perfect" piece where the number of colors needed equals the size of the biggest clique (easy peasy).
  2. Piece B: A smaller piece where the biggest clique is strictly smaller than the original city.
• Why it matters: You can keep slicing Piece B into smaller and smaller perfect pieces until the whole city is painted efficiently. It's like peeling an onion; you never get stuck in a loop.

2. The "Short-Holed" City (No Long Circles)

The Analogy: Imagine a city where every circular road is exactly 4 blocks long. There are no 5-block, 6-block, or 100-block circles. These are called Short-Holed graphs.

• The Problem: Even though these circles are short, the city can still be very complex.
• The Result: The authors found a formula to predict the maximum colors needed, depending on what other shapes are banned:
  • If the city bans a specific "Chair" shape ($K_1 + C_4$), the colors needed are roughly 4 times the square of the clique size.
  • If the city bans a "Triangle with a detached dot" ($K_1 \cup K_3$), the colors needed are roughly twice the clique size.
  • If the city bans a "Chair with a detached dot," the colors needed are roughly 16 times the clique size.

The "Leveling" Trick:
To prove this, the authors used a method called Levelling. Imagine dropping a stone in a pond.

• Level 0: The stone (1 building).
• Level 1: The first ripple (neighbors of the stone).
• Level 2: The second ripple, and so on.
  They proved that if you paint each "ripple" (level) carefully, you never need too many colors. They showed that the "ripples" don't get tangled in a way that requires infinite colors.

The Big Picture: Why Should You Care?

1. Solving the Puzzle: For decades, mathematicians have been trying to solve the "Odd Hole" puzzle. It's like trying to find a universal rule for a game that seems to have infinite variations.
2. The Conjecture: A famous mathematician named Ho`ang guessed that all cities without Odd Holes are "Perfectly Divisible" (easy to slice and paint). This paper doesn't prove the whole guess yet, but it proves it for several very specific, tricky sub-cases.
3. Real World: While this sounds like abstract math, these concepts apply to scheduling, frequency assignment (so radio stations don't interfere), and computer network design. If you can predict how many "colors" (resources) you need based on the size of your biggest group, you save money and time.

Summary in One Sentence

The authors took three very specific, complex types of "cities" (graphs) that mathematicians were struggling to understand, proved they have a hidden "onion-like" structure that allows them to be easily painted, and provided exact formulas for how many colors they will ever need.

The takeaway: Even in a chaotic world of connections, if you ban certain weird shapes, order and predictability return.

Technical Summary

Here is a detailed technical summary of the paper "The perfect divisibility and chromatic number of some odd hole-free graphs" by He, Shi, Wu, and Yao.

1. Problem Statement and Context

The paper addresses two central problems in structural graph theory:

1. Perfect Divisibility: Determining whether specific classes of graphs are "perfectly divisible." A graph $G$ is perfectly divisible if every induced subgraph $H$ with at least one edge can be partitioned into sets $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B]) < \omega(H)$. Perfect divisibility implies a polynomial bound on the chromatic number $\chi(G)$ in terms of the clique number $\omega(G)$.
2. Chromatic Number Bounds for Short-Holed Graphs: Investigating the relationship between $\chi(G)$ and $\omega(G)$ for "short-holed" graphs (graphs where every hole has length 4). While it is known that coloring odd hole-free graphs is NP-hard, finding explicit $\chi$-binding functions (where $\chi(G) \leq f(\omega(G))$) for restricted subclasses is a major open problem.

The authors specifically target graphs that are odd hole-free (containing no induced cycles of odd length $\geq 5$) and further restrict them by forbidding specific induced subgraphs (hammers, $K_{2,3}$, etc.) to establish stronger structural properties and tighter bounds.

2. Methodology

The authors employ a combination of structural graph theory techniques and inductive coloring arguments:

• Minimal Counterexample Approach: For proving perfect divisibility (Theorem 1), the authors assume the existence of a "minimally non-perfectly divisible" graph (a graph that is not perfectly divisible, but all its proper induced subgraphs are). They analyze the structure of such a graph, specifically focusing on the neighborhood of a maximum degree vertex and the properties of "anticenters" (vertices anticomplete to a specific induced subgraph).
• Leveling Arguments: For the chromatic number bounds (Theorems 3, 4, 5), the authors utilize a "leveling" technique. The vertex set is partitioned into levels $L_0, L_1, \dots, L_k$ based on distance from a root vertex. The proof proceeds by analyzing the chromatic number of each level $L_k$ relative to the previous levels ($L_{k-1}, L_{k-2}$).
• Inductive Coloring and Partitioning: The core of the coloring proofs involves partitioning a level $L_k$ into subsets based on the colors of their neighbors in the previous level. The authors then prove that these subsets are perfect (or bipartite) by showing they cannot contain specific forbidden structures (like $C_7$ or triangles), often relying on the Strong Perfect Graph Theorem.
• Forbidden Subgraph Analysis: The proofs heavily rely on deriving contradictions by showing that the assumed structure would force the existence of forbidden induced subgraphs (e.g., a hammer, $K_{2,3}$, $K_1 + C_4$, or a hole of length $\geq 5$).

3. Key Contributions and Results

The paper presents four main theorems:

Theorem 1: Perfect Divisibility of (Odd Hole, Hammer, $K_{2,3}$)-free Graphs

• Result: The class of graphs that are free of odd holes, hammers, and $K_{2,3}$ is perfectly divisible.
• Significance: This supports Hoàng's Conjecture (that all odd hole-free graphs are perfectly divisible). The authors extend previous results by Ho`ang, Brandst¨adt, and others by identifying a new class of graphs that satisfy this property.
• Mechanism: The proof demonstrates that in a minimal counterexample, the set of anticenters for an induced odd antihole must form a structure that contradicts the choice of a maximum degree vertex, thereby proving the graph must be perfectly divisible.

Theorem 2: Chromatic Bound for (Short-Holed, $K_1 + C_4$)-free Graphs

• Result: If $G$ is short-holed and $(K_1 + C_4)$-free, then $\chi(G) \leq 4\omega(\omega - 1)$.
• Significance: This improves upon the general bound for short-holed graphs ($\chi \leq 22\omega$) established by Sivaraman. It provides a quadratic bound specifically for graphs avoiding the "bull" like structure $K_1 + C_4$.
• Mechanism: The proof uses a leveling argument. It shows that vertices in level $L_k$ can be partitioned into $2(\omega-1)$sets based on their neighbors in$L_{k-1}$. Each set is proven to be perfect (specifically, it contains no$C_7$) because the absence of$K_1 + C_4$ prevents the formation of specific hole configurations.

Theorem 3: Chromatic Bound for (Short-Holed, $K_1 \cup K_3$)-free Graphs

• Result: If $G$ is short-holed and $(K_1 \cup K_3)$-free, then $\chi(G) \leq 2\omega - 1$.
• Significance: This provides a linear bound, which is significantly tighter than the quadratic bounds for general short-holed graphs. The forbidden subgraph $K_1 \cup K_3$ (an isolated vertex plus a triangle) forces the graph to be bipartite after removing the neighborhood of any vertex.

Theorem 4: Chromatic Bound for (Short-Holed, $K_1 + (K_1 \cup K_3)$)-free Graphs

• Result: If $G$ is short-holed and $(K_1 + (K_1 \cup K_3))$-free, then $\chi(G) \leq 16\omega - 24$.
• Significance: This establishes a linear bound for a slightly more complex forbidden structure. The proof follows a similar leveling strategy to Theorem 3 but requires a more intricate partitioning of levels to ensure the induced subgraphs are bipartite.

4. Significance and Future Directions

• Advancing the $\chi$-Boundedness Conjecture: The paper contributes to the broader effort to prove that odd hole-free graphs are $\chi$-bounded. By establishing specific bounds for subclasses, the authors provide evidence and techniques that may eventually lead to a proof for the general case.
• Refining Structural Understanding: The results highlight the critical role of short induced cycles (specifically length 4) and how forbidding specific "local" structures (like hammers or specific unions of cliques) drastically simplifies the global coloring properties of the graph.
• Open Problems: The authors conclude by noting that while progress is being made, proving Ho`ang's conjecture for all odd hole-free graphs remains open. They suggest future research into the $\chi$-binding functions for $(odd\ hole, hammer)$-free graphs and $(odd\ hole, K_{2,3})$-free graphs separately.

In summary, this paper successfully combines structural decomposition (anticenters, levelings) with forbidden subgraph analysis to prove perfect divisibility for a new graph class and to derive significantly improved chromatic number bounds for short-holed graphs under specific constraints.