Linear colorings of graphs

This paper investigates the properties of the linear chromatic number, a graph parameter introduced by Kun et al. as a relaxation of treedepth, and establishes improved bounds for this parameter across several graph classes.

The Gist

Imagine you are a city planner trying to organize a massive, complex city (which represents a graph in mathematics). The city has neighborhoods (vertices) connected by streets (edges). Your goal is to assign a unique "ID badge" (a color) to every resident in the city so that specific rules are followed.

This paper is about two different ways of assigning these ID badges and how they compare to each other.

The Two Rules of the Game

1. The "Centered" Rule (The Strict Boss)
This is the old, strict rule. It says: "In every single neighborhood you can walk through without leaving the city, there must be at least one person wearing a badge that no one else in that specific neighborhood is wearing."

• The Goal: You want to use as few unique badge colors as possible.
• The Problem: This is very hard to calculate. It's like trying to find the perfect seating arrangement for a huge wedding where every table needs a unique centerpiece.

2. The "Linear" Rule (The Chill Boss)
This is a newer, slightly more relaxed rule introduced by other researchers. It says: "In every single straight line of people you can walk through (a path), there must be at least one person with a unique badge."

• The Difference: The strict rule cares about any shape of neighborhood (a circle, a cluster, a maze). The chill rule only cares about straight lines.
• The Hope: Because the rule is simpler, maybe it's easier to figure out the minimum number of colors needed.

The Big Mystery: How Different Are They?

The researchers who invented the "Linear" rule wondered: "If we use the Chill Rule, how much worse does it get compared to the Strict Rule?"

They guessed that the Strict Rule would never need more than twice as many colors as the Chill Rule.

• Analogy: If the Chill Rule says you need 10 colors, the Strict Rule would never need more than 20.

However, proving this is like trying to prove that a specific type of maze can never be more than twice as confusing as a straight hallway. So far, no one has proven it for every possible city layout. The best proof we had before this paper was a messy, complicated formula that suggested the Strict Rule might need a lot more colors (like 10 times more, plus some extra math).

What This Paper Did

The authors of this paper decided to test this "Twice as Many" guess on specific types of cities to see if it holds up. They found some great news:

1. For "Simple" Cities (Trees and Caterpillars)

• Trees: Imagine a city that looks like a tree (no loops, just branches). The authors proved that for these, the Strict Rule needs at most 3.7 times the colors of the Chill Rule. This is a huge improvement over the previous messy math, bringing us much closer to the "Twice" guess.
• Caterpillars: These are trees that look like a caterpillar (a main spine with legs sticking out). For these, the guess is almost perfect! The Strict Rule needs at most one extra color compared to the Chill Rule.

2. For "Structured" Cities (Chordal and Circular-Arc)
These are cities with very specific geometric shapes (like overlapping circles or intervals). The authors showed that for these, the number of colors needed grows in a predictable, manageable way (quadratically), which is much better than the wild growth we feared.

3. When They Are Exactly the Same
The paper found several types of cities where the Strict Rule and the Chill Rule are actually identical. In these cases, you don't need to worry about the difference at all; the minimum number of colors is the same for both. Examples include "complete multipartite graphs" (think of a city where everyone is friends with everyone except their own family) and "complements of rook's graphs" (a chessboard pattern).

The "Obstruction" Hunt

The researchers also played a game of "What breaks the rules?"
They asked: "What is the smallest, simplest city layout that forces us to use 4 colors?"
They found a specific list of 8 "monster" shapes (like a 4-cycle with specific legs, or a long path) that act as the "forbidden" patterns. If your city doesn't contain any of these monsters, you are guaranteed to be able to color it with 3 or fewer colors. This is like finding the specific "bad ingredients" that make a cake fail; if you avoid them, the cake always works.

The Computer Science Part

Finally, they looked at the computer side of things:

• Hard Mode: They proved that figuring out the exact number of colors for the "Chill Rule" is computationally very hard (NP-complete) for certain types of cities. It's like trying to solve a Sudoku puzzle that is impossible to solve quickly.
• Easy Mode (for small numbers): However, if you only care about small numbers of colors (like, "Can we do it with 5 colors?"), they found a fast algorithm to check. It's like having a magic scanner that can instantly tell you if a small puzzle is solvable, even if solving the whole thing is hard.

The Bottom Line

This paper is a massive step forward in understanding the relationship between these two coloring rules.

• The Good News: For many important types of graphs (trees, caterpillars, structured shapes), the "Chill Rule" is almost as good as the "Strict Rule." The gap between them is tiny.
• The Open Question: The big mystery remains: Is the Strict Rule always at most twice the Chill Rule for any city?
  • The authors haven't solved the whole puzzle yet, but they've cleared away a lot of the fog and shown that for the most common and interesting types of graphs, the answer is a resounding "Yes, it's very close."

In short, they took a complex mathematical conjecture, tested it on various real-world-like structures, and found that the universe is much more orderly and predictable than we previously thought.

Technical Summary

Here is a detailed technical summary of the paper "Linear colorings of graphs" by Hilaire, Krnc, Milanič, and Raymond.

1. Problem Statement and Motivation

The paper investigates the linear chromatic number ($\chi_{lin}$), a graph parameter introduced by Kun et al. [KOPS21] as a relaxation of the centered chromatic number ($\chi_{cen}$), which is equivalent to the well-studied treedepth.

• Definitions:
  • A centered coloring assigns colors to vertices such that every connected subgraph has a unique color (a "center").
  • A linear coloring assigns colors such that every path has a unique color.
  • Since paths are connected subgraphs, every centered coloring is linear, implying $\chi_{lin}(G) \leq \chi_{cen}(G)$.
• The Core Question: How large can the gap between $\chi_{cen}(G)$ and $\chi_{lin}(G)$ be?
  • Kun et al. proved a polynomial relationship: $\chi_{cen}(G) \leq \chi_{lin}(G)^{10} \cdot (\log \chi_{lin}(G))^{O(1)}$.
  • They conjectured a linear bound: Conjecture 1.2: $\chi_{cen}(G) \leq 2 \cdot \chi_{lin}(G)$ for all graphs $G$.
  • Previous work showed the ratio can approach 2 for certain $P_5$-free chordal graphs, suggesting the factor of 2 might be tight.

The paper aims to improve the known bounds for specific graph classes and investigate the structural properties and algorithmic complexity of $\chi_{lin}$.

2. Methodology

The authors employ a combination of structural graph theory, extremal graph theory, and algorithmic techniques:

1. Structural Decomposition: They utilize the relationship between treedepth, treewidth, and unavoidable subgraphs. Specifically, they rely on the result by Czerwinski, Nadara, and Pilipczuk [CNP21] (Theorem 3.2), which states that graphs with large centered chromatic number must contain either large treewidth or a large subcubic tree as a subgraph.
2. Pseudogrids and Grid Minors: They use the concept of $k \times k$ pseudogrids and the Grid Minor Theorem to relate treewidth to the presence of grid minors, which in turn forces high linear chromatic numbers.
3. Case Analysis on Graph Classes: The authors perform detailed structural analysis on specific classes (e.g., caterpillars, complete multipartite graphs, co-rook's graphs) to determine exact values or tight bounds for $\chi_{lin}$ and $\chi_{cen}$.
4. Obstruction Sets: They adapt techniques from Dvořák et al. [DGT12] regarding treedepth obstructions to characterize the minimal forbidden subgraphs for bounded linear chromatic number.
5. Complexity Theory: They analyze the computational complexity using reductions from known NP-complete problems and Courcelle's Theorem for Fixed-Parameter Tractability (FPT).

3. Key Contributions and Results

A. Improved Bounds for Graph Classes

The paper provides significant improvements over the general polynomial bound for several graph families. The results are summarized in Table 1 of the paper:

• Minor-Closed Classes: For any proper minor-closed graph class, the authors prove a quadratic bound: $\chi_{cen}(G) = O(\chi_{lin}(G)^2)$.
• Bounded Treewidth: For graphs with treewidth $tw(G) \leq t$, they establish a linear bound:
  $$\chi_{cen}(G) \leq 3.7 \cdot (t+1) \cdot \left(\chi_{lin}(G) + \frac{1}{\log 3}\right)$$
  This improves upon previous non-constant logarithmic bounds for trees.
• Trees: Specifically for trees, the bound is refined to $\chi_{cen}(T) \leq 3.7 \cdot \chi_{lin}(T)$. This improves the previous bound of $(\log \Delta) \cdot \chi_{lin}(T)$ (where $\Delta$ is the maximum degree).
• Intersection Graphs: The quadratic bound is extended to chordal graphs and circular-arc graphs.
• Caterpillars: The authors prove that for caterpillars, the parameters differ by at most 1: $\chi_{cen}(T) \leq \chi_{lin}(T) + 1$. They also show this bound is tight.

B. Classes Where Parameters Coincide

The paper identifies several graph classes where $\chi_{lin}(G) = \chi_{cen}(G)$, confirming Conjecture 1.2 with a factor of 1 for these cases:

• $(P_3 + P_1)$-free graphs: Every linear coloring is centered.
• $(Claw, Net)$-free graphs: This class includes proper interval graphs.
• Complete Multipartite Graphs: The authors determine the exact value: $\chi_{lin}(G) = \chi_{cen}(G) = n - p + 1$ (where $n$ is the order and $p$ is the size of the largest part).
• Complements of Rook's Graphs: Exact values are determined for these graphs.

C. Obstruction Sets

The authors investigate the minimal forbidden subgraphs (obstructions) for graphs with $\chi_{lin}(G) \leq k$.

• They prove that for any $k$, the set of obstructions with respect to the subgraph relation is finite.
• They explicitly list the obstruction sets for $k \in \{1, 2, 3\}$. For $k=3$, the set consists of 14 graphs (including $K_4$, $P_8$, and various cycles and subdivisions), derived by modifying the known obstruction set for treedepth.

D. Algorithmic Complexity

• NP-Completeness: The authors prove that computing the linear chromatic number is NP-complete for cobipartite graphs. This is achieved by showing that for connected cobipartite graphs, $\chi_{lin} = \chi_{cen}$, and leveraging the known NP-completeness of treedepth on these graphs.
• FPT Algorithm: They provide a Fixed-Parameter Tractable (FPT) algorithm to decide if $\chi_{lin}(G) \leq k$. The algorithm runs in $O(n)$ time (for fixed $k$) by:
  1. Bounding the treewidth of graphs with $\chi_{lin} \leq k$ (using the polynomial relation $\chi_{cen} \leq \chi_{lin}^{11}$).
  2. Expressing the property of having a linear $k$-coloring as a Monadic Second-Order logic formula ($MSO_2$).
  3. Applying Courcelle's Theorem on the resulting bounded treewidth graph.

4. Significance and Open Problems

• Refining the Gap: The paper significantly narrows the gap between the known polynomial upper bound and the conjectured linear bound for many important graph classes. While the general conjecture $\chi_{cen} \leq 2\chi_{lin}$ remains open, the authors show it holds (or holds with a small additive constant) for trees, caterpillars, and various intersection graphs.
• Algorithmic Implications: The FPT result is crucial for practical applications, as it allows for efficient recognition of graphs with small linear chromatic numbers, which is relevant for algorithmic pipelines in bounded expansion graph classes.
• Open Question: The paper concludes by restating the main conjecture and posing a specific open question: What is the supremum $c$ of the ratio $\chi_{cen}(T)/\chi_{lin}(T)$ for trees? The authors know $c \geq \log 3 \approx 1.58$ (from Theorem 2.11) but the exact value remains unknown.

In summary, this work provides a comprehensive exploration of linear colorings, offering tighter structural bounds, exact characterizations for specific classes, and a complete complexity picture, thereby advancing the understanding of the relationship between path-based and connectivity-based graph colorings.