On the chromatic profile for tripartite graphs and beyond

Published 10 Apr 2026 in math.CO | (2604.09394v1)

Abstract: Let $H$ be a graph and let $δχ(H,r)$ denote the infimum of $c$ such that every $H$-free graph with minimum degree at least $cn$ is $r$-colorable. The \textit{chromatic profile} of $H$ is defined to be the values of $δχ(H,r)$ as $r$ varies. Erdős and Simonovits described this graph parameter as ``too complicated", and Allen, Böttcher, Griffiths, Kohayakawa, and Morris posed its determination for every graph $H$ as an open problem \cite[Problem~45]{ABGKM2013}, emphasizing its expected difficulty. In this paper, we resolve the case $r=2$ for every graph $H$ with $χ(H)=3$. We show that the set of possible values of $δχ(H,2)$ with $χ(H)=3$ is finite and discrete: $${δχ(H,2):χ(H)=3}=\left{\frac{1}{2},\frac{2}{5},\frac{2}{7},\frac{1}{4},\frac{2}{9},\frac{1}{5},\frac{2}{11},\frac{1}{6}\right}.$$ Furthermore, we provide a complete structural characterization of the graphs $H$ associated with each threshold value. Moreover, we extend the classical chromatic profile result for triangle to color-critical graphs $H$ with $g_{\mathrm{odd}}(H)=χ(H)=3$. Our approach introduces a useful auxiliary parameter. Motivated by the notion of vertex-extendability of Liu, Mubayi, and Reiher \cite{liu2023unified}, we define the {\it vertex-extendable threshold} of $H$, denoted by $δ{\mathrm{ext}}(H,r)$, as the infimum of $c\in (0,1)$ so that for every $H$-free graph $G$ on $n$ vertices, the existence of a vertex $v \in V(G)$ with $χ(G - v) \leq r$ combined with $δ(G)\ge cn$ implies that $G$ is $r$-colorable. A key structural consequence is that $δχ(H,2) = \max\left{δχ(C{2k+1},2),δ{\mathrm{ext}}(H,2)\right},$ where $H$ is a color-critical graph with $χ(H)=3$ and $g{\mathrm{odd}}(H)=2k+1$ for $k\geq 2$.

Abstract PDF Upgrade to Chat

Authors (3)

Summary

The paper identifies the complete set of possible values for δχ(H,2) in tripartite graphs with color-critical structures.
Using modular proofs with removal, intersection, and blow-up lemmas, the authors derive sharp degree thresholds for 2-colorability.
Extremal constructions such as G1(n)–G6(n) illustrate the discrete chromatic spectrum, linking classical Turán problems with modern graph techniques.

Chromatic Profiles for Tripartite Graphs: Discrete Structure and Structural Classification

Introduction and Motivation

The paper "On the chromatic profile for tripartite graphs and beyond" (2604.09394) addresses the longstanding question regarding the chromatic profile $\delta_\chi(H,r)$ for graphs $H$ with $\chi(H)=3$ . The key parameter, $\delta_\chi(H, r)$ , denotes the infimum $c$ such that every $H$ -free graph $G$ on $n$ vertices with $\delta(G) \geq c n$ is $r$ -colorable. For $H$ 0 and $H$ 1, the authors completely determine the set of possible values of $H$ 2, connecting extremal graph constructions and local structural graph parameters.

The study is motivated by classic results from Mantel, Turán, and the Erdős–Stone–Simonovits theorem, and builds on foundational work on the chromatic profile for triangles and odd cycles, e.g., Haggkvist, Jin, and Brandt–Thomassé. Allen et al. posed the explicit challenge of fully determining $H$ 3 for arbitrary $H$ 4 [ABGKM2013].

Main Results: Discrete Classification and Structural Dichotomy

The central achievement is the complete determination of the chromatic profile $H$ 5 for all graphs $H$ 6 with $H$ 7, proving that the set is finite and discrete: $H$ 8 Each value is sharp and corresponds to an explicit family of tripartite critical graphs. The classification relies on a dichotomy: non-color-critical graphs realize $H$ 9 following Erdős–Simonovits, while color-critical cases are classified by odd girth and containment in a finite library of extremal constructions.

Figure 1: The extremal constructions $\chi(H)=3$ 0 through $\chi(H)=3$ 1, each realizing a distinct threshold in the chromatic profile for tripartite graphs.

Extremal Constructions and Graph Families

A salient aspect of the paper is the construction of extremal templates $\chi(H)=3$ 2, each engineered to show the sharpness of the thresholds and to serve as counterexamples for specific $\chi(H)=3$ 3.

$\chi(H)=3$ 4, ..., $\chi(H)=3$ 5: These are iterative blow-ups of odd cycles and certain join operations, precisely connected with the families $\chi(H)=3$ 6. For example, $\chi(H)=3$ 7 is a “hexapartite” construction originally due to Häggkvist, realizing the threshold $\chi(H)=3$ 8.

The structural classification depends on the odd girth $\chi(H)=3$ 9 and whether $\delta_\chi(H, r)$ 0 embeds into one or more of these infinite families. The flowchart gives a quick decision procedure for the value of $\delta_\chi(H, r)$ 1 based on these containment criteria.

Vertex-Extendable Threshold and Reduction to Core Parameters

An auxiliary innovation is the introduction of the vertex-extendable threshold $\delta_\chi(H, r)$ 2: the minimum $\delta_\chi(H, r)$ 3 so that, in an $\delta_\chi(H, r)$ 4-free graph $\delta_\chi(H, r)$ 5 with $\delta_\chi(H, r)$ 6 and the property that $\delta_\chi(H, r)$ 7 is $\delta_\chi(H, r)$ 8-colorable for some vertex $\delta_\chi(H, r)$ 9, $c$ 0 must itself be $c$ 1-colorable. The main technical reduction, proved via iterative applications of the Removal Lemma and Zarankiewicz-type intersection bounds, is: $c$ 2 where $c$ 3 and $c$ 4 is color-critical. The paper further provides exact values for $c$ 5 as a function of $c$ 6’s containment in the extremal families.

Proof Techniques and Structural Tools

The proof strategy is modular and combines probabilistic, spectral, and intersection-type arguments:

Removal lemma and blow-up arguments to control forbidden substructures in almost extremal graphs.
Intersection lemmas (see Lemma \ref{lem-intersection}) to extract large bipartite complete subgraphs from degree conditions.
Flowchart and case analysis: For color-critical graphs, exhaustive checking of odd-girth/embedding conditions using the structure of templates, reducing the potentially infinite classification to a finite decision tree.
Figure 2: Case analysis for neighborhood structure provides the basis for ruling out color-critical subgraphs or extracting large induced bipartite subgraphs.

These methods yield sharp upper bounds, while the constructed extremal graphs give matching lower bounds, establishing tightness.

Implications for Turán-type Problems and Regularity

The discrete spectrum and their associated extremal graphs connect with regular Turán numbers: For each $c$ 7 in the discrete list, maximal regular $c$ 8-free graphs reach the threshold degree prescribed by $c$ 9. The results also extend and clarify the landscape for odd cycles and help map out the chromatic profile for further families ( $H$ 0, $H$ 1) as directions for future work.

Theoretical and Practical Significance

Sharp bounding of chromatic profiles for any tripartite or color-critical $H$ 2 allows for direct application in extremal combinatorics, coloring, and sparse random graphs subject to forbidden structures.
Modular framework: Introduction of vertex-extendability gives a recursive parameter suitable for generalization to higher chromatic numbers.

The strategies deployed can serve as a blueprint for addressing further open cases of Allen et al.'s Problem 45.

Future Directions

The combinatorial reductions to finite template containment, and the successful full solution for $H$ 3 and $H$ 4, indicate that progress on higher $H$ 5 or $H$ 6 will hinge on new generalizations of the vertex-extendable paradigm. Determining $H$ 7 for $H$ 8-chromatic $H$ 9 is highlighted as the next critical step. Extension of these methods to chromatic profiles of oriented graphs (digraphs) is also posed.

Conclusion

The paper achieves a complete, discrete classification of $G$ 0 for tripartite and color-critical graphs, introducing refined structural parameters and techniques. The multifaceted approach—combining extremal constructions, intersection lemmas, and recursive threshold definitions—resolves questions open since Erdős–Simonovits. The results advance the understanding of the interplay between forbidden subgraphs, degree constraints, and colorability, and provide foundational tools for future progress on chromatic profiles.