Edge-colouring and orientations: applications to degree-boundedness and $χ$-boundedness

Arnab Char, Ken‐ichi Kawarabayashi, Lucas Picasarri‐ArrietaarXiv 2025 · DOI · arXiv

This paper, titled "Edge-colouring and orientations: applications to degree-boundedness and $\chi$-boundedness," provides a new structural tool for graph theorists. It explores the relationship between edge-coloring, graph orientations, and the fundamental properties of vertex degrees and chromatic numbers.

TL;DR

The authors prove that any 2-edge-colored graph with a sufficiently high minimum degree must contain a monochromatic induced subgraph that also maintains a high minimum degree. They use this "density-preserving" Ramsey-type result to prove that several complex classes of graphs—including odd-signable and Burling graphs—are degree-bounded and, in some cases, polynomially $\chi$-bounded.

What Problem Does This Paper Address?

In structural graph theory, researchers often want to know if a graph class is "well-behaved." Two major ways to measure this are:

  1. Degree-boundedness: Does a high minimum degree in a graph necessarily force the existence of a specific simple structure (like a large complete bipartite graph $K_{s,s}$)?
  2. $\chi$-boundedness: Is the chromatic number ($\chi$) of a graph bounded by a function of its largest clique size ($\omega$)?

The authors tackle a specific challenge: if you color the edges of a "dense" graph (one with a high minimum degree), can you still find a "dense" subgraph where all edges are the same color? While classical Ramsey theory tells us we can find monochromatic cliques, those cliques might be very small compared to the original graph's degree. This paper seeks to find monochromatic subgraphs that inherit the "density" (minimum degree) of the parent graph.

Methods

The paper is a theoretical work employing the probabilistic method and building upon "heavy hitter" results in extremal combinatorics.

  • Probabilistic Subsampling: To prove the core theorem (Theorem 1.1), the authors use random vertex subsets. By selecting vertices with specific probabilities and applying Chernoff and Markov inequalities, they demonstrate that a monochromatic induced subgraph with the desired degree properties exists with positive probability.
  • Inductive Recurrence: They extend the result from 2-edge-colorings to $k$-edge-colorings using a standard recurrence argument.
  • Leveraging Existing Machinery: The proofs rely on several landmark results, including:
  • Kühn and Osthus (2004): Regarding induced even subdivisions in graphs of large minimum degree.
  • Kwan, Letzter, Sudakov, and Tran (2020): Regarding the existence of large cliques or induced bipartite graphs with large average degrees.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs rather than empirical data or benchmarks.

Key Insights and Ideas

  • Density is Persistent: The most significant insight is that high minimum degree is a "robust" property. You can't "hide" high degree by splitting edges into two colors; at least one color will retain a structural backbone of high degree.
  • The Power of Antidirectedness: The authors highlight the importance of antidirected structures (where every vertex is either a source or a sink). They show that avoiding certain antidirected forests or cycles is a defining characteristic of degree-bounded graph classes.
  • Bridging Coloring and Orientations: The paper provides a elegant bridge: problems about graph orientations (how we direct edges) can often be translated into edge-coloring problems, which are then solvable using the paper's new density-preserving theorem.
  • Polynomial Bounds: For certain classes, like those admitting "even-hole-free" $k$-colorings, the authors don't just prove $\chi$-boundedness; they prove polynomial $\chi$-boundedness, which is a much stronger and more desirable property in the field.

Key Results

  • Theorem 1.1 (The Core Result): For any $k$ and $d$, there exists a threshold such that every $k$-edge-colored graph with minimum degree $\delta(G) \ge f(k, d)$ contains a monochromatic induced subgraph $H$ with $\delta(H) \ge d$.
  • Odd-Signable Graphs: The authors prove that the class of odd-signable graphs is degree-bounded and polynomially $\chi$-bounded.
  • Characterizing Oriented Forests: They prove that for an oriented graph $F$, the class of $F$-free graphs is degree-bounded if and only if $F$ is an antidirected forest.
  • Burling Graphs: They provide a new proof/extension showing that Burling graphs (a famous class of triangle-free graphs with high chromatic number) are degree-bounded.

Limitations and Future Work

  • Tightness of Bounds: The authors acknowledge that their calculated bound for the core theorem ($f_{1.1}$) is triple exponential in $d$. They explicitly state this is "certainly not tight" and leave the search for a more efficient bound to future researchers.
  • Linearity: While they proved polynomial $\chi$-boundedness for certain classes ($\mathcal{G}_k$), they pose Problem 3.2: Is this class actually linearly $\chi$-bounded?
  • Oriented Forest Characterization: While they characterized degree-boundedness for $F$-free graphs, they leave open the characterization of which oriented forests $F$ result in $\chi$-bounded classes (Problem 3.8).

Summary updated

Abstract

We prove that every $2$-edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph whose minimum degree remains large. As a consequence, we deduce that some classes of graphs are degree-bounded. A class $\mathcal{G}$ is {\it degree-bounded} if, for every integer $s$, there exists $d=d(s)$ such that every graph $G\in \mathcal{G}$ either contains $K_{s,s}$ or has minimum degree at most $d$. We obtain that the following classes are degree-bounded: (i) for every $k$, the graphs $G$ whose edge-set can be $k$-coloured such that no even hole of $G$ is monochromatic; (ii) for every fixed antidirected forest $F$, the graphs admitting an orientation without any induced copy of $F$; (iii) for every $\ell\geq 4$, the graphs admitting an orientation without any induced antidirected cycle of length at least $\ell$. For $k=2$, class (i) contains odd-signable graphs. Class (ii) characterises the oriented graphs $H$ such that the class of graphs admitting an orientation without any induced copy of $H$ is degree-bounded. For $\ell=5$, class (iii) contains Burling graphs. In case (i) and case (iii) for $\ell=4$, we further obtain that the classes are polynomially $χ$-bounded.
BibTeX
@misc{char2025edge,
  author = {Arnab Char and Ken‐ichi Kawarabayashi and Lucas Picasarri‐Arrieta},
  title = {{Edge-colouring and orientations: applications to degree-boundedness and $χ$-boundedness}},
  year = {2025},
  eprint = {2506.23054},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.23054},
  howpublished = {arXiv},
}

Loading related content...

Figure