The fractional chromatic number binding functions of (cap, even hole)-free graphs
- School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
* Corresponding author: Chenglong Deng, chenglongdeng@zjnu.edu.cn.
This article belongs to an issue that is still in progress. Bibliographic details may change before formal publication in December, 2026.
Abstract
A hole is an induced cycle of length at least four, and a cap is a hole together with a vertex adjacent to exactly two consecutive vertices of the hole. We prove that if \(q\ge 2\) and \(G\) is a \((\mathrm{cap},\mathrm{even\ hole})\)-free graph with no odd hole of length at most \(2q-1\), then \(\chi_f(G)\le {2q+1\over 2q}\omega(G)\). The bound is best possible, as shown by clique blowups of \(C_{2q+1}\).
Keywords: fractional chromatic number; stable set polytope; Kneser graph; even hole; cap; clique blowup
Mathematics Subject Classification: 05C15 (primary), 05C75 (secondary)
1. Introduction
A graph \(G\) consists of a set \(V(G)\) of vertices, and a set \(E(G)\) of edges, where each edge is a pair of distinct vertices. We write \(uv \in E(G)\) or \(u \sim v\) if \(u,v \in V(G)\) are vertices of \(G\), and the pair \(\{u,v\} \in E(G)\) is an edge of \(G\). We say vertices \(u\) and \(v\) are adjacent if \(uv \in E(G)\). A proper \(k\)-coloring of a graph \(G\) is a mapping \(\phi: V(G) \to [k] =\{1,2,\ldots, k\}\) such that \(\phi(u) \ne \phi(v)\) for any two adjacent vertices \(u\) and \(v\). The chromatic number of \(G\) is defined as \[\chi(G) = \min\{k: G \text{ admits a proper $k$-coloring}\}.\]
Graph coloring provides a unifying model for resource distribution problems under pairwise exclusion constraints. These include scheduling, register allocation in compilers, channel assignment, etc.
A fundamental problem in graph coloring is which graphs \(G\) have a large chromatic number. A clique in \(G\) is a set \(X\) of pairwise adjacent vertices. The clique number \(\omega(G)\) of \(G\) is the cardinality of a maximum clique in \(G\). As all vertices in a clique need to be colored with distinct colors, \(\omega(G) \le \chi(G)\). On the other hand, Erdős [8] showed that for any positive integers \(k,g\), there are graphs of girth at least \(g\) and chromatic number at least \(k\), where the girth of \(G\) is the length of the shortest cycle in \(G\). In particular, there are graphs \(G\) with \(\omega(G)=2\) and \(\chi(G)\) arbitrarily large. So \(\chi(G)\) is not upper bounded by any function of \(\omega(G)\) for general graphs \(G\).
In 1975, Gyárfás introduced the concept of \(\chi\)-bounded family of graphs: A class \(\mathcal G\) of graphs is called \(\chi\)-bounded if there is a function \(f: \mathbb{N} \to \mathbb{N}\) such that \(\chi(G)\le f(\omega(G))\) for every \(G\in\mathcal G\). The problem of which families of graphs are \(\chi\)-bounded has been studied extensively in the literature (see [15] for a survey).
For two graphs \(G\) and \(H\), we say \(G\) is \(H\)-free if \(G\) does not contain an induced subgraph isomorphic to \(H\). If \(\mathcal H\) is a family of graphs, then \(G\) is \(\mathcal H\)-free if \(G\) is \(H\)-free for every \(H\in\mathcal H\). The main problem in this area is to determine for which \(\mathcal H\), the family of \(\mathcal H\)-free graphs is \(\chi\)-bounded.
A hole is an induced cycle of length at least four, and a hole is even or odd if the induced cycle is even or odd. It follows from the result of Erdős that the \(\mathcal H\)-free graphs are not \(\chi\)-bounded, unless \(\mathcal H\) contains a forest or the lengths of holes in the graphs in \(\mathcal H\) are unbounded. Gyárfás [9] and Sumner [16] conjectured independently that if \(\mathcal H\) contains a forest, then the \(\mathcal H\)-free graphs are \(\chi\)-bounded (equivalently, for any tree \(T\), the family of \(T\)-free graphs is \(\chi\)-bounded). This conjecture has received a lot of attention and has been confirmed for some special families of trees [15], but remains open in general. Gyárfás [10] also conjectured that the family of (odd hole)-free graphs, the family of (hole of length at least \(\ell\))-free graphs, and the family of (odd hole of length at least \(\ell\))-free graphs are \(\chi\)-bounded. These conjectures remained open for more than 40 years and were confirmed by Scott and Seymour [14], Chudnovsky, Scott and Seymour [3], and Chudnovsky, Scott, Seymour and Spirkl [4], respectively.
Given a \(\chi\)-bounded family \(\mathcal G\) of graphs, a natural problem is to find an optimal binding function. It is very rare that optimal binding functions for graph families are known. For most families of graphs that are known to be \(\chi\)-bounded, the proven binding functions are enormous, usually exponential tower functions. For example, the bounding function for odd hole-free graphs \(G\) proved by Scott and Seymour is \(\chi(G) \le 2^{2^{\omega(G)+2}}\). These functions are believed to be far from optimal.
The family of (even hole)-free graphs has a simpler structure. Chudnovsky and Seymour [5] proved that every even-hole-free graph \(G\) has a bisimplicial vertex, i.e., a vertex whose neighbors are covered by two cliques. This implies \(\chi(G)\le 2\omega(G)-1\). A cap is a hole together with a vertex adjacent to exactly two consecutive vertices of the hole. The structure of \((\mathrm{cap},\mathrm{even\ hole})\)-free graphs is even simpler. Cameron, da Silva, Huang and Vuskovic proved that \((\mathrm{cap},\mathrm{even\ hole})\)-free graphs \(G\) have \(\chi(G)\le 3\omega(G)/2\) [1]. This upper bound was improved by Wu and Xu, and Xu in [17, 18]. Very recently, Chen, Xu and Xu proved the optimal binding function for \((\mathrm{cap},\mathrm{even\ hole})\)-free graphs [2]: every \((\mathrm{cap},\mathrm{even\ hole})\)-free graph \(G\) satisfies \(\chi(G)\le \left\lceil {5\over 4}\omega(G)\right\rceil\). This bound is reached by the lexicographic product of \(C_5\) and \(K_k\): \(\chi(C_5[K_k])=\lceil 5k/2 \rceil =\lceil 5\omega(G)/4 \rceil\). Chen, Xu and Xu further proved that every \((\mathrm{cap},\mathrm{even\ hole},5\mathrm{-hole})\)-free graph \(G\) satisfies \( \chi(G)\le \left\lceil {7\over 6}\omega(G)\right\rceil\). This bound is also sharp, as \(\chi(C_7[K_k])=\lceil 7k/3 \rceil =\lceil 7\omega(G)/6 \rceil\). Chen, Xu and Xu conjectured the following general pattern: if \(q\ge 2\) and \(G\) is a \((\mathrm{cap},\mathrm{even\ hole})\)-free graph with no odd hole of length at most \(2q-1\), then \( \chi(G)\le \left\lceil {2q+1\over 2q}\omega(G)\right\rceil\). Their result confirms this conjecture for \(q \le 3\). After the submission of this paper, this conjecture has been verified independently in [7] and [11].
In this paper, we prove the fractional version of this conjecture. The proof uses polytopes, which is conceptually different from the structural coloring used in both [7] and [11].
A stable set of a graph \(G\) is a set of pairwise non-adjacent vertices of \(G\). We denote by \(\mathcal{I}(G)\) the set of all stable sets of \(G\).
A fractional coloring of a graph \(G\) is a mapping \(\lambda: \mathcal{I}(G) \to [0,1]\) such that \(\sum_{ I \in \mathcal{I}(G), I\ni v } \lambda(I) \ge 1\) for each vertex \(v\). The weight of a fractional coloring \(\lambda\) of \(G\) is \(w(\lambda) = \sum_{I \in \mathcal{I}(G)}\lambda(I)\). The fractional chromatic number \(\chi_f(G)\) is the infimum weight of a fractional coloring of \(G\).
For a fractional coloring \(\lambda\) of \(G\), if \(\lambda(I) \in \{0,1\}\) for each stable set \(I\), then \(\{I: \lambda(I)=1\}\) is a family of stable sets that covers \(V(G)\). This is equivalent to a proper coloring of \(G\), using \(w(\lambda)\) colors. So for any graph \(G\), \(\chi_f(G) \le \chi(G)\), and it is well-known that the difference \(\chi(G)-\chi_f(G)\) can be arbitrarily large.
The following is the main result of this paper.
Let \(q\ge2\). If \(G\) is a \((\mathrm{cap},\mathrm{even\ hole})\)-free graph with no odd hole of length at most \(2q-1\) , then \(\chi_f(G)\le{2q+1\over 2q}\omega(G)\).
The bound is best possible, since the clique blowup \(C_{2q+1}[K_t]\) satisfies \(\omega(C_{2q+1}[K_t])=2t\) and \(\chi_f(C_{2q+1}[K_t])=t{2q+1\over q} = {2q+1\over 2q}\omega(C_{2q+1}[K_t]) \).
2. Some preliminary lemmas
Assume \(G\) is a graph and \(x,y,z\) are three consecutive vertices of a hole in \(G\). By adding an ear to \(G\) with \(x,z\) as attachments, we mean adding an \(x\)-\(z\)-path \(P\) whose internal vertices are disjoint from \(V(G)\) and adding edges joining \(y\) to some vertices of \(P\). A wheel \(W\) is a graph obtained from a cycle \(C\) by adding a vertex \(v\) adjacent to at least three vertices of \(C\). The added vertex is called the center of \(W\), and the cycle \(C\) is called the ring of \(W\). The ear addition is called good if the following hold:
\(y\) has an odd number of neighbors on \(V(P)\).
There is no wheel \(W\) in \(G\) with \(v\) as its center, \(x,y,z \) on the ring and \(vy\in E(G)\).
There is no wheel \(W\) in \(G\) with \(y\) as its center, and both \(x\) and \(z\) are neighbors of \(y\) in \(W\).
Let \(G\) be a graph, and let \(f\) be an assignment of integers 0 and 1 to its edges. A subgraph \(H\) of \(G\) is said to be odd if \(\sum_{e \in E(H)} f(e)\) is odd. The graph \(G\) is said to be odd-signable if it has an assignment of 0 and 1 to its edges such that every induced cycle is odd.
Note that every even hole-free graph \(G\) is odd-signable by labeling each edge of \(G\) with the integer 1. We shall use the following two lemmas.
If \(F\) is a graph and each vertex \(v\in V(F)\) is replaced by a clique \(Q_v\), with all edges between \(Q_u\) and \(Q_v\) added whenever \(uv\in E(F)\), then the resulting graph is a clique blowup of \(F\). A universal clique in a graph is a clique whose vertices are universal, i.e., adjacent to every other vertex. A clique cutset of a graph \(F\) is a clique \(K\) in \(F\) such that \(F-V(K)\) has more connected components than \(F\).
[6] Let \(G\) be a triangle-free graph with at least three vertices that is not the cube and has no clique cutset. Then \(G\) is odd-signable if and only if it can be obtained, starting from a hole, by a sequence of good ear additions.
[1] Let \(G\) be a \((\mathrm{cap},4\text{-hole})\)-free graph that contains a hole and has no clique cutset. Let \(F\) be a maximal induced subgraph of \(G\) with at least 3 vertices that is triangle-free and has no clique cutset. Then \(G\) is obtained from \(F\) by first blowing up vertices of \(F\) into nonempty cliques, and then adding a universal clique.
For a subset \(X\) of \(V(G)\), the incidence vector of \(X\), denoted by \(1_X\), is the mapping \(1_X: V(G) \to \{0,1\}\) defined as \[ 1_X(v) = \begin{cases} 1, &\text{ if $v \in X$} \cr 0, &\text{ otherwise}. \cr \end{cases} \] The stable set polytope \(\st(G)\) of \(G\) is the convex hull of the incidence vectors of all the stable sets of \(G\), i.e., \[ \st(G)=\conv\{\mathbf 1_I:I\in \mathcal I(G)\}. \] Equivalently, a vector \(p\) belongs to \(\st(G)\) if and only if there is a probability distribution on the stable sets of \(G\) such that \(p_v\) is the probability that a random stable set contains \(v\).
Assume \(G\) is the vertex-disjoint union of \(G_1\) and \(G_2\). For \(p_i \in \st(G_i)\), we extend \(p_i\) to a vector in \(\mathbb{R}^{V(G)}\) by letting \(x_v=0\) for \(v \in V(G_{3-i})\).
If \(G\) is the vertex-disjoint union of \(G_1\) and \(G_2\), then \begin{eqnarray*} \st(G) &=& \{p_1+p_2: p_1 \in \st(G_1), p_2 \in \st(G_2)\}. \end{eqnarray*}
Note that \(X\) is an independent set of \(G\) if and only if \(X \cap V(G_i)\) is an independent set of \(G_i\). Thus \(1_X \in \st(G)\) if and only if \(1_{X \cap V(G_i)} \in \st(G_i)\) for \(i=1,2\).
If for \(i=1,2\), \(\lambda_i\) is a probability distribution on \(\mathcal I(G_i)\) such that \(p_i(v)\) is the probability that a random stable set contains \(v\) for \(v \in V(G_i)\), then \(\lambda(I) =\lambda_1(I \cap V(G_1)) \lambda_2(I \cap V(G_2))\) is a probability distribution on \(\mathcal I(G)\) such that \((p_1+p_2)(v)\) is the probability that a random stable set contains \(v\) for \(v \in V(G)\).
□Let \(w:V(G)\to\mathbb R_{\ge0}\) be a weight function. The weight of a clique \(K\) of \(G\) is \(w(K) = \sum_{v \in K} w(v)\), and the weighted clique number of \((G,w)\) is \(\omega_w(G) = \max\{w(K): K \text{ is a clique of } G\}\). A fractional coloring of \((G,w)\) is a mapping \(\lambda: \mathcal I(G) \to [0,\infty)\) such that for each vertex \(v\), \(\sum_{I \ni v}\lambda(I) \ge w(v)\). The fractional chromatic number \(\chi_f(G,w)\) is defined as \[ \chi_f(G,w) = \inf\{ \sum_{I\in\mathcal I(G)}\lambda(I): \lambda \text { is a fractional coloring of $(G,w)$}\}. \]
There are a few equivalent definitions of fractional chromatic number (cf. [13]). A \((p,q)\)-coloring of a graph \(G\) is a mapping \(\phi\) that assigns a set \(\phi(v)\) of \(q\) colors from \([p]\) such that for every edge \(uv\), \( \phi(u) \cap \phi(v) =\emptyset\). It is well-known [13] that the fractional chromatic number of \(G\) is the infimum of \(p/q\) such that \(G\) admits a \((p,q)\)-coloring. A \((p,q)\)-coloring of \((G,w)\) is defined similarly, except that for each vertex \(v\), \(\phi(v)\) is a set of \(\lceil {qw(v)} \rceil\) colors, instead of a set of \(q\) colors. The fractional chromatic number of \((G, w)\) is the infimum of \(p/q\) such that \((G,w)\) admits a \((p,q)\)-coloring. When \(G\) is finite, the infimum is achieved and hence can be replaced by minimum.
Let \(G\) be a clique blowup of a graph \(F\), and let \(w(v)=|Q_v|\). Then \( \omega(G)=\omega_w(F) \) and \( \chi_f(G)=\chi_f(F,w)\).
Each clique of \(G\) is obtained from a clique of \(F\) by a clique blowup. Thus \(\omega(G) = \omega_w(F)\). If \(\phi\) is a \((p,q)\)-coloring of \((F,w)\), then for each vertex \(v\) of \(F\), partition the color set \(\phi(v)\) into \(w(v)\) subsets of size \(q\), and assign these \(w(v)\) subsets to the vertices of \(Q_v\). Then we obtain a \((p,q)\)-coloring of \(G\). Hence \(\chi_f(G) \le \chi_f(F,w)\).
Conversely, if \(\psi\) is a \((p,q)\)-coloring of \(G\), then for each vertex \(v\) of \(F\), let \(\psi(v) = \cup_{x \in Q_v}\psi(x)\). We obtain a \((p,q)\)-coloring of \((F,w)\). Hence \(\chi_f(F, w) \le \chi_f(G)\), and therefore \(\chi_f(G) = \chi_f(F,w)\).
□Let \(K>0\). Then \(\chi_f(G,w)\le K\) if and only if \(w/K\in\st(G)\).
Suppose first that \(\chi_f(G,w)\le K\). Choose a fractional coloring \(\lambda: \mathcal I(G) \to [0,\infty)\) of \((G,w)\) of total weight at most \(K\). By adding the remaining weight to the empty stable set, we may assume that its total weight is exactly \(K\). Then \( \lambda'_I = \lambda(I)/K \) is a probability distribution on the stable sets. Let \(p_v = \sum_{I \ni v} \lambda'_I\) for each vertex \(v\). Then \(p\in\st(G)\). The covering constraints give \(p\ge w/K\). Since \(\st(G)\) is down-closed, \(w/K\in\st(G)\).
Conversely, if \(w/K\in\st(G)\), then multiplying a convex representation of \(w/K\) by \(K\) gives a fractional coloring of \((G,w)\) of total weight \(K\). Hence \(\chi_f(G,w)\le K\).
□To prove that \(w/K \in \st(G)\), we consider the edge relaxation of the stable set polytope \(\qst(G)\) of \(G\), in which the vectors satisfy only the vertex and edge constraints.
For a graph \(G\), define \[ \qst(G)=\{x\in \mathbb R^{V(G)}:0\le x_v\le 1\text{ for all }v, \text{ and }x_u+x_v\le 1\text{ for all }uv\in E(G)\}. \] The constraints for the points in \(\qst(G)\) are satisfied by \(1_I\) for any independent set \(I\) of \(G\). Hence, \[ \st(G)\subseteq \qst(G). \] The inclusion can be strict. For example, if \(G=C_5\) and \(x_v=1/2\) for all vertices \(v\), then \(x\in \qst(C_5)\), since every edge has endpoint sum equal to \(1\). But \(x\notin \st(C_5)\), since for any stable set \(I\) of \(C_5\), \(\sum_{ v \in V(C_5)} 1_I(v) \le 2\), whereas \[ \sum_{v\in V(C_5)}x_v=5/2>2. \]
An extreme point of a polytope is a point which is not a convex combination of two distinct points of the polytope. The following standard half-integrality property of the edge relaxation \(\qst(G)\) of the stable set polytope was proved by Nemhauser and Trotter [12]. We include a short proof of this lemma for completeness.
Every extreme point \(x\) of \(\qst(G)\) is half-integral, that is, \(x_v\in\{0,{1\over 2},1\}\) for every \(v\in V(G)\). Moreover, if \(A=\{v\in V(G):x_v=1\}\) and \(B=\{v\in V(G):x_v={1\over 2}\}\), then \(A\) is a stable set, there is no edge between \(A\) and \(B\), and \(x=\mathbf 1_A+{1\over 2}\mathbf 1_B\).
Let \(x\) be an extreme point of \(\qst(G)\), and let \(U=\{v\in V(G):0<x_v<1\}\). Let \(Q\) be the graph with vertex set \(U\) and edge set \(\{uv\in E(G[U]):x_u+x_v=1\}\).
We first show that every component of \(Q\) contains an odd cycle. Suppose not, and \(C\) is a bipartite component of \(Q\) with bipartition \((R,S)\). For sufficiently small \(\varepsilon>0\), define two vectors \(x^+\) and \(x^-\) as follows. For \(v\notin V(C)\), let \(x^+_v=x^-_v=x_v\). For \(v\in R\), let \(x^+_v=x_v+\varepsilon\) and \(x^-_v=x_v-\varepsilon\). For \(v\in S\), let \(x^+_v=x_v-\varepsilon\) and \(x^-_v=x_v+\varepsilon\).
We claim that \(x^+,x^-\in\qst(G)\) if \(\varepsilon\) is small enough. The bounds \(0\le x_v^\pm\le 1\) hold because all vertices of \(C\) belong to \(U\). If \(uv\) is an edge of \(Q[V(C)]\), then \(u\) and \(v\) lie in different parts of the bipartition, and hence \(x_u^\pm+x_v^\pm=x_u+x_v=1\). If \(uv\in E(G)\) is not an edge of \(Q[V(C)]\), then either \(x_u+x_v<1\) or \(u, v \notin C\) and hence none of \(x_u, x_v\) is changed. In any case, the constraint \(x_u+x_v \le 1\) remains valid for sufficiently small \(\varepsilon\). Hence \(x^+,x^-\in\qst(G)\).
Moreover, \(x^+\ne x^-\) and \(x={1\over 2}(x^++x^-)\). This contradicts the assumption that \(x\) is an extreme point of \(\qst(G)\). Therefore, every component of \(Q\) contains an odd cycle.
Now consider a component of \(Q\). As \(x_u+x_v=1\) for every edge \(uv\), the values \(x_v\) on an odd cycle alternate between \(t\) and \(1-t\). This forces \(t=1-t\), and so \(t={1\over 2}\). Therefore, every vertex of \(U\) has value \({1\over 2}\). The vertices outside \(U\) have value \(0\) or \(1\) according to the definition of \(U\). Thus, every coordinate of \(x\) belongs to \(\{0,{1\over 2},1\}\).
Let \(A=\{v\in V(G):x_v=1\}\) and \(B=\{v\in V(G):x_v={1\over 2}\}\). If two vertices of \(A\) were adjacent, then the edge constraint would give \(2\le 1\), impossible. If a vertex of \(A\) was adjacent to a vertex of \(B\), then the edge constraint would give \(1+{1\over 2} \le 1\), a contradiction. Hence \(A\) is stable and there is no edge between \(A\) and \(B\). Finally, by the definitions of \(A\) and \(B\), we have \(x=\mathbf 1_A+{1\over 2}\mathbf 1_B\).
□3. Fractional coloring of the skeleton
This section considers the case that \(G\) is triangle-free. A fractional coloring of a graph can be defined by homomorphisms to Kneser graphs. For positive integers \(n \ge 2k\), the Kneser graph \(\KG(n,k)\) has vertices all \(k\)-subsets of \([n]\), in which \(A\) and \(B\) are adjacent if \(A \cap B = \emptyset\). A homomorphism from a graph \(G\) to a graph \(H\) is a mapping \(\phi: V(G) \to V(H)\) that preserves edges, i.e., if \(uv \in E(G)\), then \(\phi(u)\phi(v) \in E(H)\). It follows from the definition that an \((n,k)\)-coloring of \(G\) is equivalent to a homomorphism from \(G\) to \(\KG(n,k)\). Therefore \(\chi_f(G) = \min\{n/k: G \text{ admits a homomorphism to } \KG(n,k)\}\). The following lemma is well-known. Again, for the completeness of the paper, we include a proof of this lemma.
Let \(A\) and \(B\) be neighbors of \(Y\) in \(\KG(2q+1,q)\). If \(A\ne B\), then there is a walk of length \(2q-1\) from \(A\) to \(B\). Moreover, if \(\ell \ge 2q+1\) is odd, then there is a walk of length \(\ell\) from \(A\) to \(B\), whether or not \(A=B\). Equivalently, if a path of odd length \(\ell\ge 2q-1\) has its two end vertices precolored by two distinct neighbors of \(Y\), then this precoloring extends to a \((2q+1,q)\)-coloring of the path.
Let \(n=2q+1\) and the vertices of \(\KG(n,q)\) be the \(q\)-subsets of \(\mathbb Z_n\). For \(i\in\mathbb Z_n\), define \[ S_i=\{iq,iq+1,\ldots,iq+q-1\}\pmod n. \] Then \( S_0S_1\cdots S_{n-1}S_0 \) is an \(n\)-cycle in \(\KG(n,q)\).
On this cycle, the two neighbors \(S_1\) and \(S_{n-1}\) of \(S_0\) are joined by a path of length \(n-2\). Since the automorphism group of \(\KG(n,q)\) induced by permutations of the ground set is transitive on triples \((Y,A,B)\) with \(A\) and \(B\) distinct neighbors of \(Y\), any two distinct neighbors of \(Y\) are joined by a walk of length \(n-2\).
If a longer odd length \(\ell\ge n\) is required, insert backtracking walks of length \(2\). If \(A=B\) and \(\ell\ge n\), go once around an \(n\)-cycle through \(A\), and again insert backtracking walks of length \(2\) if necessary.
The final statement follows by assigning the successive vertices of the walk as the colors on the successive vertices of the path.
□Let \(F\) be obtained from \(F'\) by a good ear addition. Suppose that \(F\) is triangle-free, even-hole-free, and has no odd hole of length at most \(2q-1\) (\(q \ge 2\)). Then every \((2q+1,q)\)-coloring \(\varphi\) of \(F'\) can be extended to a \((2q+1,q)\)-coloring of \(F\).
Let \(P=x_0x_1\cdots x_m\) be the added good ear. Let \(y\in V(F')\) be the vertex such that \(x_0,y,x_m\) are consecutive vertices of a hole of \(F'\), and \(y\) has an odd number of neighbors on \(P\).
List the neighbors of \(y\) on \(P\), in their order along \(P\), as \[ z_0=x_0,z_1,\ldots,z_{2s}=x_m. \]
Let \(\varphi\) be a \((2q+1,q)\)-coloring of \(F'\). The colors \(\varphi(z_0)\) and \(\varphi(z_{2s})\) are both neighbors of \(\varphi(y)\) in \(\KG(2q+1,q)\). Write \(A=\varphi(z_0)\) and \(B=\varphi(z_{2s})\), allowing the possibility that \(A=B\).
Since the neighbors of \(\varphi(y)\) in \(\KG(2q+1,q)\) are exactly the \(q\)-subsets of \([2q+1]\setminus \varphi(y)\), there are \(q+1\ge3\) such neighbors. Hence, we can choose a neighbor \(C\) of \(\varphi(y)\) such that \(C\ne A\) and \(C\ne B\).
We color the vertices \(z_1,\ldots,z_{2s-1}\) by setting \[ \varphi(z_i)= \begin{cases} C, & \text{if } i \text{ is odd},\\ A, & \text{if } i \text{ is even}. \end{cases} \] Then every consecutive pair \(z_i,z_{i+1}\) receives distinct colors, and every \(z_i\) receives a neighbor of \(\varphi(y)\).
For each \(i=0,1,\ldots,2s-1\), put \(\ell_i=|E(z_iPz_{i+1})|\). The cycle \(yz_iPz_{i+1}y\) is induced, and hence is an odd hole of length at least \(2q-1\). Thus \(\ell_i\) is odd and \(\ell_i\ge 2q-3\).
Since \(\varphi(z_i)\) and \(\varphi(z_{i+1})\) are distinct neighbors of \(\varphi(y)\), Lemma 3.1 extends the coloring to every segment \(z_iPz_{i+1}\), and hence to \(P\). The chosen colors on the \(z_i\)'s are all disjoint from \(\varphi(y)\), and there are no other edges from the interior of \(P\) to \(F'\). Therefore the coloring extends to \(F\).
□If \(q \ge 2\), \(F\) is triangle-free, even-hole-free, and has no odd hole of length at most \(2q-1\), then \(F\) has a \((2q+1,q)\)-coloring. Consequently, \[ \chi_f(F)\le {2q+1\over q}. \]
Suppose not, and choose a counterexample \(F\) with \(|V(F)|\) minimum.
If \(F\) is not connected, then each connected component admits a \((2q+1,q)\)-coloring, and the union of these colorings is a \((2q+1,q)\)-coloring of \(F\), a contradiction. If \(F\) has a clique cutset \(K\), then since \(F\) is triangle-free, \(|K|\le 2\). Let \(C_1,\ldots,C_t\) be the components of \(F-K\), and put \(F_i=F[V(C_i)\cup K]\). Each \(F_i\) satisfies the same assumptions and has fewer vertices, so it has a \((2q+1,q)\)-coloring \(\varphi_i\). As \(|K| \le 2\), the colorings \(\varphi_i\) can be made to agree on \(K\). Thus they combine to a \((2q+1,q)\)-coloring of \(F\), a contradiction.
Thus, \(F\) is connected and has no clique cutset. If \(F\) has no hole, then \(F\) is a forest and is \(2\)-colorable. If \(F\) is a hole of length \(\ell\), then \(\ell\) is odd and \(\ell\ge 2q+1\). By Lemma 3.1, \(F\) admits a homomorphism to \(\KG(2q+1,q)\).
Therefore, \(F\) is not a hole. By Lemma 2.3, \(F\) is obtained from a proper induced subgraph \(F'\) by a good ear addition (note that \(F\) is not a cube because it has no even hole). By the minimality of \(F\), \(F'\) has a \((2q+1,q)\)-coloring. By Lemma 3.2, such a coloring extends to a \((2q+1,q)\)-coloring, a contradiction.
□4. Weighted fractional coloring of the skeleton
For a connected graph \(F \ne K_1\) and a weight function \(w:V(F)\to\mathbb R_{\ge 0}\), let \[\omega_w(F)=\max\{\sum_{v\in K}w(v):K\text{ is a clique of }F\}.\] If \(F\) is triangle-free, then every clique has size at most two. Hence the condition \(\omega_w(F)\le W\) is equivalent to \(w(v) \le W\) for every vertex \(v\) and \(w(u)+w(v)\le W\) for every edge \(uv\in E(F)\).
Let \(q\ge 2\), and let \(F\) be a triangle-free, even-hole-free with no odd hole of length at most \(2q-1\). Then for every weight function \(w:V(F)\to \mathbb R_{\ge 0}\), \[ \chi_f(F,w)\le {2q+1\over 2q}\omega_w(F). \]
Put \(c={2q+1\over 2q}\) and \(W=\omega_w(F)\). If \(W=0\), then \(w\equiv 0\), and the assertion is trivial. Assume \(W>0\), and set \(\overline w=w/W\). By Lemma 2.8, it is enough to prove \(\overline w/c\in \st(F)\).
Since \(F\) is triangle-free and \(\omega_{\overline w}(F)=1\), we have \(\overline w(v)\le 1\) for every \(v\in V(F)\) and \(\overline w(u)+\overline w(v)\le 1\) for every edge \(uv\in E(F)\). Thus \(\overline w\in \qst(F)\).
We shall prove the stronger statement \(\qst(F)\subseteq c\st(F)\). Since \(\qst(F)\) is a polytope and \(\st(F)\) is convex, it suffices to prove that \(x/c\in \st(F)\) for every extreme point \(x\) of \(\qst(F)\).
Let \(x\) be an extreme point of \(\qst(F)\). By Lemma 2.9, \(x=\mathbf 1_A+{1\over 2}\mathbf 1_B\), where \(A=\{v:x_v=1\}\) is a stable set and there is no edge between \(A\) and \(B=\{v:x_v=1/2\}\).
The induced subgraph \(F[B]\) is still triangle-free, even-hole-free, and has no odd hole of length at most \(2q-1\). By Theorem 3.3, \(\chi_f(F[B])\le {2q+1\over q}=2c\). By Lemma 2.8, \({1\over 2c}\mathbf 1_B\in \st(F[B])\). As \(\frac{1}{c} 1_A \in \st(F[A])\) and there is no edge between \(A\) and \(B\), it follows from Lemma 2.5 that \(x/c = \frac{1}{c} 1_A + {1\over 2c}\mathbf 1_B \in \st(F)\). By Lemma 2.8, \(\chi_f(F,w)\le cW={2q+1\over 2q}\omega_w(F)\).
□5. Proof of the Main Theorem
Put \(c={2q+1\over 2q}\). Suppose that the theorem is false, and choose a counterexample \(G\) with \(|V(G)|\) minimum. Thus \(\chi_f(G)>c\omega(G)\).
If \(G\) contains no hole, then \(G\) is a chordal graph and hence \(\chi_f(G)=\omega(G)\le c\omega(G)\), a contradiction. If \(G\) has a clique cutset \(K\), then let \(G_1,\ldots,G_t\) be the blocks separated by \(K\). By the minimality of \(G\), each \(G_i\) has a \((p,q)\)-coloring \(\phi_i\) of \((G_i,w)\) with \(p/q \le c\omega(G)\). By permuting the colors, we may assume that \(\phi_1,\ldots, \phi_t\) agree on \(K\) and hence their union is a \((p,q)\)- coloring of \(G\), a contradiction. If \(G\) has a nonempty universal clique \(U\), then \(\chi_f(G)=|U|+\chi_f(G-U)\) and \(\omega(G)=|U|+\omega(G-U)\). By the minimality of \(G\), \(\chi_f(G-U)\le c\omega(G-U)\). Therefore \(\chi_f(G)\le |U|+c\omega(G-U)\le c(|U|+\omega(G-U))=c\omega(G)\), a contradiction.
Therefore \(G\) contains a hole, has no clique cutset, and has no universal clique. Since \(G\) is even-hole-free, it is also \(4\)-hole-free. By Lemma 2.4, \(G\) is a clique blowup of a maximal triangle-free induced subgraph \(F\) with no clique cutset. For each \(v\in V(F)\), let \(Q_v\) be the clique replacing \(v\), and put \(w(v)=|Q_v|\).
The graph \(F\) is triangle-free, even-hole-free, and has no odd hole of length at most \(2q-1\). By Lemma 4.1, \(\chi_f(F,w)\le c\omega_w(F)\). By Lemma 2.7, \(\chi_f(G)=\chi_f(F,w)\) and \(\omega(G)=\omega_w(F)\). Hence \(\chi_f(G)\le c\omega(G)\), a contradiction.
Therefore \(\chi_f(G)\le {2q+1\over 2q}\omega(G)\).
□Acknowledgements
The idea of using polytopes \(\st(G)\) and \(\qst(G)\) for the study of fractional version of Chen-Xu-Xu's conjecture was suggested by ChatGPT.
plain ref
References
- K. Cameron, Murilo V. G. da Silva, S. Huang, and K. Vušković. Structure and algorithms for \((\mathrm{cap},\mathrm{even\ hole})\)-free graphs. Discrete Mathematics, 341(2):463–473, 2018.
- R. Chen, B. Xu, and Y. Xu. The optimal binding function for \((\mathrm{cap},\mathrm{even\ hole})\)-free graphs. arXiv preprint arXiv:2506.19580, 2025.
- M. Chudnovsky, A. Scott, and P. Seymour. Induced subgraphs of graphs with large chromatic number. III. Long holes. Combinatorica, 37(6):1057–1072, 2017.
- M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes. J. Combin. Theory Ser. B, 140:84–97, 2020.
- M. Chudnovsky and P. Seymour. Even-hole-free graphs still have bisimplicial vertices. J. Combin. Theory Ser. B, 161:331–381, 2023.
- M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Triangle-free graphs that are signable without even holes. J. Graph Theory, 34(3):204–220, 2000.
- Chenglong Deng and Xuding Zhu. Optimal binding function for (cap,even hole)-free graphs with no short odd holes, arXiv: 2607.27850, 2026.
- P. Erdős. Graph theory and probability. Canadian J. Math., 11:34–38, 1959.
- A. Gyárfás. On Ramsey covering-numbers. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, volume Vol. 10 of Colloq. Math. Soc. János Bolyai, pages 801–816. North-Holland, Amsterdam-London, 1975.
- A. Gyárfás. Problems from the world surrounding perfect graphs. In Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), volume 19, pages 413–441, 1987.
- Feng Liu, Shuang Sun, and Yan Wang. Optimal coloring of \(\{\mathrm{cap},\mathrm{even\ hole}\}\)-free graphs with no short odd holes, arXiv: 2607.25396, 2026.
- G. L. Nemhauser and L. E. Trotter, Jr. Vertex packings: structural properties and algorithms. Math. Programming, 8:232–248, 1975.
- Edward R. Scheinerman and Daniel H. Ullman. Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley / John Wiley & Sons, New York, 1997.
- A. Scott and P. Seymour. Induced subgraphs of graphs with large chromatic number. I. Odd holes. J. Combin. Theory Ser. B, 121:68–84, 2016.
- A. Scott and P. Seymour. A survey of \(\chi\)-boundedness. J. Graph Theory, 95(3):473–504, 2020.
- D. P. Sumner. Subtrees of a graph and the chromatic number. In The theory and applications of graphs (Kalamazoo, Mich., 1980), pages 557–576. Wiley, New York, 1981.
- R. Wu and B. Xu. A note on chromatic number of \((\mathrm{cap},\mathrm{even\ hole})\)-free graphs. Discrete Mathematics, 342(3):898–903, 2019.
- Y. Xu. A better upper bound on the chromatic number of \((\mathrm{cap},\mathrm{even\text{-}hole})\)-free graphs. Discrete Mathematics, 344(11):112581, 2021.
How to cite
Chenglong Deng, Xuding Zhu. “The fractional chromatic number binding functions of (cap, even hole)-free graphs.” College Mathematics 1, no. 1 (2026): 13-20.