ISSN 2590-9770
The Art of Discrete and Applied Mathematics 6 (2023) #P2.11
https://doi.org/10.26493/2590-9770.1491.14a
(Also available at http://adam-journal.eu)
Subgraphs of Kneser graphs with large girth and
large chromatic number
Bojan Mohar*
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
Hehui Wu†
Shanghai Center for Math. Sci., Fudan University, Shanghai, China
Received 13 October 2021, accepted 18 October 2022, published online 9 December 2022
Abstract
It is well known that for any integers k and g, there is a graph with chromatic number
at least k and girth at least g. In 1960s, Erdős and Hajnal conjectured that for any k and g,
there exists a number h(k, g), such that every graph with chromatic number at least h(k, g)
contains a subgraph with chromatic number at least k and girth at least g. The Erdős-
Hajnal Conjecture has been recently proposed in the setting of the fractional chromatic
number. In support of the original and the modified conjecture, we prove that every Kneser
graph, whose (fractional) chromatic number is sufficiently large, contains a subgraph of
large girth, whose (fractional) chromatic number is large.
Keywords: Kneser graph, graph coloring, chromatic number, fractional chromatic number.
Math. Subj. Class.: 05C15
1 Introduction
A well known result, proved by Erdős [3] in 1950s, tells us that for every k and g, there
exists a graph with chromatic number at least k and girth at least g. In 1960s, Erdős and
Hajnal [4] proposed the following conjecture.
*Corresponding author. Supported in part by the NSERC Discovery Grant R611450 (Canada), by the Canada
Research Chairs program, and by the Research Project J1-2452 of ARRS (Slovenia). On leave from IMFM,
Jadranska 19, 1000 Ljubljana.
†Part of this work was done while the author was a PIMS Postdoctoral Fellow at the Department of Mathe-
matics, Simon Fraser University, Burnaby, B.C.
E-mail addresses: mohar@sfu.ca (Bojan Mohar), hhwu@fudan.edu.cn (Hehui Wu)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 6 (2023) #P2.11
Conjecture 1.1 (Erdős and Hajnal (1969)). For any integers k and g, there exists a value
h(k, g) such that every graph G with χ(G) ≥ h(k, g) contains a subgraph with chromatic
number at least k and girth at least g.
This conjecture has been resolved for for g = 4 and arbitrary k by Rödl in 1977 [10],
but it remains open for any larger girth. Recently, the authors extended Rödl’s result to the
setting of the fractional chromatic number χf by proving the following statement.
Theorem 1.2 ([9]). For every real number t ≥ 1, there exists a positive number k(t)
such that every graph G with χf (G) ≥ k(t) contains a triangle-free subgraph H with
χf (H) ≥ t.
Let us recall that the fractional chromatic number χf (G) of a graph G is the minimum
value of the following linear program:∑
I∈I(G)
yI , subject to
∑
I∈I(G,v)
yI ≥ 1 for each v ∈ V (G), (1.1)
where I(G) denotes the family of all independent vertex-sets of G, I(G, v) is the family of
all those independent sets which contain the vertex v, and yI is a nonnegative real variable
for each independent set I .
A version of the Erdős-Hajnal Conjecture for the fractional chromatic number has been
proposed in [9].
Conjecture 1.3. For all t ≥ 1 and g ≥ 3, there exists k(t, g) such that every graph G with
χf (G) ≥ k(t, g) contains a subgraph H of girth at least g and with χf (H) ≥ t.
Let us recall that the vertex-set of the Kneser graph KG(n, r) consists of all r-sets of
elements from {1, . . . , n}, and two such sets are adjacent if they are disjoint. It may be
assumed that r ≤ n/2. It is known [7] (see also [5]) that χ(KG(n, r)) = n − 2r + 2 and
that χf (KG(n, r)) = n/r.
There is a tight relationship between Kneser graphs and the fractional chromatic num-
ber of general graphs. Namely, the following result holds (see, e.g. [5]).
Theorem 1.4. For every graph G, we have the following:
χf (G) = min{ nr | G has a homomorphism into KG(n, r)}.
Theorem 1.4 shows that the first step towards a certification of Conjecture 1.3 should be
its verification for the family of Kneser graphs. In this note we first observe the following.
Theorem 1.5. For every k and g, every Kneser graph KG(n, r) with n/r sufficiently large
contains a subgraph whose fractional chromatic number is at least k and whose girth is at
least g.
This statement is an easy corollary of the fact that KG(n, r) contains a complete sub-
graph of order N = ⌊n/r⌋ and the fact proved in [3] that sufficiently large complete graph
contains a subgraph of girth at least g and with fractional chromatic number at least k.1
1The proof or Erdős is actually for the usual chromatic number, but it is based on estimating the largest
independent set, so it applies also for the fractional chromatic number.
B. Mohar et al.: Subgraphs of Kneser graphs with large girth and large chromatic number 3
The fact that the Erdős-Hajnal Conjecture is so resistant opens the question whether
graphs with bounded fractional chromatic number (and large chromatic number) would
still satisfy Conjecture 1.1. Therefore, it is natural to ask whether Conjecture 1.1 holds for
Kneser graphs. The following theorem, which is the main result of this note, confirms that
this is the case.
Theorem 1.6. For every k and g, every Kneser graph KG(n, r) with n − 2r sufficiently
large contains a subgraph whose chromatic number is at least k and whose girth is at
least g.
Proof of Theorem 1.6 occupies the rest of the paper.
2 Blow-ups and Kneser graphs
Our proof of Theorem 1.6 is motivated by the approach that was developed by Bollobás
and Sauer [2] and generalized by Zhu [11]. They used their method to find uniquely k-
colorable graphs of large girth and graphs of large girth that have unique homomorphism
into any given core (a graph that does not have a homomorphism onto a proper subgraph
of itself). The same approach was used in the setting of digraphs in [6].
The approach in [2, 11] used large blow-ups of graphs which have a homomorphism
into some graph K but have no homomorphisms into some other fixed graph L.
However, the basic results in [2, 11] are not sufficiently strong to imply Theorem 1.6.
We will thus develop the required strengthening which occupies the rest of this section.
Given a graph H , the blow-up of H with power m, denoted by H(m), is the graph ob-
tained from H by replacing each vertex a ∈ V (H) by an independent set Va of cardinality
m (called the blow-up of the vertex), and for each edge ab in H , adding a complete bipartite
graph isomorphic to Km,m between Va and Vb. The subgraph of H(m) replacing the edge
ab will be referred to as the blow-up of that edge.
Let us recall that a graph L is said to be a core if every homomorphism h : L → L is
an automorphism of L. A graph G is L-colorable if there exists a homomorphism G → L.
We have the following statement.
Theorem 2.1. Let L be a graph of order t = |L|, and let G be a graph that is not L-
colorable. Suppose that g ≥ 3 and that ∆ ≥ ∆(G) is an integer such that
(a) (t∆)(g−2)/(2g) > 4(1 + log t) and
(b) log(t∆) ≥ 10s−1 + 8.
If m is an integer that is larger than t(t∆)2g−4, then G(m) contains a subgraph with girth
more than g that is not L-colorable.
Let us observe that the proof of the main result in [11] contains a statement that is very
close to the above theorem. However, the bound on m in [11] depends not only on the size
of L and the maximum degree of G, but involves the number of vertices of G, which is not
sufficient for our application.
To prove Theorem 2.1, we will need the following fact from [2, 11].
Lemma 2.2. Let G be a graph that is not L-colorable, and let H be a subgraph of G(m).
Suppose that for any edge ab ∈ E(G) and for any subsets X,Y contained in the blow-ups
Va and Vb of a and b, respectively, with |X| ≥ m|L| , |Y | ≥
m
|L| , there is an edge between X
and Y in H . Then H is not L-colorable.
4 Art Discrete Appl. Math. 6 (2023) #P2.11
In the proof of Theorem 2.1 we will take a random subgraph H of G(m), obtained
by selecting each edge independently with probability (mt )
1
4l−1, and will prove that with
positive probability thus obtained subgraph H has no short cycles, and for any edge ab ∈
E(G) and for any pair X,Y contained in the respective blow-ups of a and b, and with
|X| ≥ mt , |Y | ≥
m
t , there is an edge between X and Y in H . To prove this, we will use
the following asymmetric form of the Lovász Local Lemma (see [1]).
Theorem 2.3 (Lovász Local Lemma). Let A = {A1, . . . , An} be a finite set of events
in the probability space Ω. For A ∈ A let Γ(A) denote a subset of A such that A is
independent from the collection of events A \ ({A} ∪ Γ(A)). If there exists an assignment
of real numbers y : A → (0, 1) to the events such that
∀A ∈ A : Pr(A) ≤ y(A)
∏
B∈Γ(A)
(1− y(B))
then the probability of avoiding all events in A is positive. In particular,
Pr
(
A1 ∧ . . . ∧An
)
≥
∏
A∈A
(1− y(A)).
Proof of Theorem 2.1. We may assume that L is connected. If t = 1, the statement is
obvious. If t = 2, then L = K2. In this case the proof is clear, since there is an odd cycle
with length more than g in G(m). Thus we may assume henceforth that t ≥ 3.
Let s = mt , λ =
1
4g and p = s
λ−1. Let H be a random subgraph of G(m) obtained by
picking each edge in G(m) independently at random with probability p.
If C is a cycle in G(m) of length at most g, let AC be the event that all edges of C
appear in H . Then Pr(AC) = p|C| = s(λ−1)|C|.
Let B be a copy of Ks,s as a subgraph of a blow-up of an edge in G, let AB be the event
that H contains none of the edges of B. Then Pr(AB) = (1− p)s
2 ≈ e−ps2 = e−s1+λ .
To prove that there exists a subgraph of G(m) with girth at least g that is not L-colorable,
we will use Lemma 2.2. We just need to show
Pr
(( ∧
|C|≤g
AC
)
∧
( ∧
B∼=Ks,s
AB
))
> 0.
This will be confirmed by applying the asymmetric form of the Lovász Local Lemma (The-
orem 2.3) to the two types of events together.
Suppose that C is a cycle of length |C| ≤ g. As the maximum degree in G(m) is at
most m∆ = st∆, there are at most |C|(st∆)j−2 cycles of length j in G(m) that share
edges with C, and there are at most |C|
(
m
s
)2
copies of Ks,s that share edges with C.
Suppose that B is a copy of Ks,s. There are at most s2(st∆)j−2 cycles of length j in
G(m) that share edges with B, and there are at most
(
m
s
)2
copies of Ks,s that share edges
with B.
For the Lovász Local Lemma, let y0 = y(AB) = e−0.5s
1+λ ≈ Pr(AB)0.5, and for each
cycle C of length |C| ≤ g, let y|C| = y(AC) = Pr(AC)1−λ = s−(1−λ)
2|C| < s(2λ−1)|C|.
We just need to show:
(1) Pr(AC) ≤ y|C|
(∏
3≤j≤g(1− yj)|C|(st∆)
j−2
)
(1− y0)|C|(
m
s )
2
;
B. Mohar et al.: Subgraphs of Kneser graphs with large girth and large chromatic number 5
(2) Pr(AB) ≤ y0
(∏
3≤j≤g(1− yj)s
2(st∆)j−2
)
(1− y0)(
m
s )
2
.
Let us take the logarithm on each side of the above inequalities, and use the fact that
0.9 log(1 − z) > −z (when z is close to 0 as it appears to be in our case when z = y0 or
yj). After simplifying, we see that it suffices to verify the following inequalities:
(3) 0.9λ(1− λ) log s ≥
∑
3≤j≤g s
(2λ−1)j(st∆)j−2 + e−0.5s
1+λ(st
s
)2
.
(4) 0.4s1+λ ≥
∑
3≤j≤g s
(2λ−1)js2(st∆)j−2 + e−0.5s
1+λ(st
s
)2
.
In order to prove (4), we first observe that:∑
3≤j≤g
s(2λ−1)js2(st∆)j−2 =
∑
3≤j≤g
s2λj(t∆)j−2
< 1.1s2λg(t∆)g−2
= 1.1s0.5(t∆)g−2.
By the assumption of the theorem, s > (t∆)2g−4. Thus, (t∆)g−2 < s0.5, and we have∑
3≤j≤g
s(2λ−1)js2(st∆)j−2 < 1.1s
Similarly, we also have
∑
3≤j≤g s
(2λ−1)j(st∆)j−2 < 1.1s−1, which will be used to
prove (3).
As
(
st
s
)2
< (et)2s, we have
e−0.5s
1+λ
(
st
s
)2
< (e−0.5s
λ
(et)2)s = (e−0.5s
λ+2+2 log t)s.
Using the assumption that s > (t∆)2g−4 and then using the assumption (a) from the state-
ment of the theorem, we obtain that
sλ > (t∆)
2g−4
4g > 4(1 + log t).
This implies that, e−0.5s
1+λ(st
s
)2
< 1.
Now, using the assumption (b), we see that
0.9λ(1− λ) log s ≥ 0.9(1− λ)2g − 4
4g
log(t∆) > 18 log(t∆) ≥ 1.1s
−1 + 1.
This implies that 0.4s1+λ ≥ 1.1s + 1, and we conclude that both inequalities (3) and (4)
are true.
In summary, if m = st ≥ t(t∆)2g−4, by the asymmetric form of the Lovász Local
Lemma, the event that H has no cycles of length at most g and every Ks,s as a subgraph
of a blow-up of an edge has at least one edge, has positive probability. This means that
there is a subgraph H of G(m) with these properties. Hence, by Lemma 2.2, H is not
L-colorable.
6 Art Discrete Appl. Math. 6 (2023) #P2.11
The last ingredient needed in the forthcoming proofs is the following result from
[8, Theorem 3.3] which shows that Kneser graphs contain blow-ups of smaller Kneser
graphs with large power.
Theorem 2.4. Let n, k, s, and t be nonnegative integers such that 0 < k < n and t < ks.
The Kneser graph KG(ns, ks− t) contains the blow-up of KG(n, k) with power
(
k(s−1)
t
)
as a subgraph. Furthermore, when t < s, it contains the blow-up of KG(n, k) with power(
ks
t
)
, and when t = s, it contains the blow-up of KG(n, k) with power
(
ks
t
)
− k.
3 Proof of Theorem 1.6
From Theorem 2.1, we know that graphs that are blow-ups of smaller graphs with suffi-
ciently large power satisfy the Erdős-Hajnal Conjecture. In particular, Kneser graphs are
such examples. This can be used to derive Theorem 1.6.
Let k and g be the parameters from the statement of the theorem. We may assume that k
and g are both large. Let KG(2n, n− 2x) be a Kneser graph with large chromatic number.
Since χ(KG(2n, n− 2x)) = 4x+2, this just means that x is large in terms of k and g. Let
t = x/k. By Theorem 2.4, KG(2n, n − 2x) contains a blow-up of KG(2n/t, (n − x)/t)
with power m =
(
(n−x)(t−1)/t
x
)
. (Note that KG(r, s) contains KG(r− 1, s) as a subgraph,
and thus, with some neglect of technicalities, we may assume that x/k, 2n/t, (n − x)/t,
etc. are integers.) Each vertex of KG(2n/t, (n− x)/t) has degree
(
(n+x)/t
(n−x)/t
)
=
(
(n+x)/t
2x/t
)
,
which is at most
∆ := ((n+ x)/t)2x/t =
(nk
x
+ k
)2k
.
In order to apply Theorem 2.1, we need power m ≥ k(k∆)2g−4 of a graph with chro-
matic number at least k. In the following we assume x is large in terms of g and k. Then
we may assume that ∆ is sufficiently large so that the conditions (a) and (b) of Theorem 2.1
are satisfied.
Let us first consider the case when n > x/
(
1
2 −
1
2k
)
. If we write nx = 2 + 2z, this
condition implies that z ≥ 1k . If x > k
2, then
n− x
x
· t− 1
t
≥ 1 + z (3.1)
and
n
x
+ 1 = 3 + 2z < (1 + z)x/2. (3.2)
Suppose, moreover, that x ≥ 10gk2 log k. Then
k2g(2k+1) < (1 + z)x/2. (3.3)
Using inequalities (3.1) – (3.3), we obtain:
k(k∆)2g−4 = k2g−3
(nk
x
+ k
)2k(2g−4)
<
( (n− x)(t− 1)/t
x
)x
<
(
(n− x)(t− 1)/t
x
)
= m.
B. Mohar et al.: Subgraphs of Kneser graphs with large girth and large chromatic number 7
On the other hand, when x is large enough and n ≤ x/
(
1
2 −
1
2k
)
, then n − 2x ≤ n/k
and KG(2n, n− 2x) contains a blow-up of KG(k, 1) = Kk with large power.
Thus, we can apply Theorem 2.1 and conclude that KG(2n, n−2x) contains a subgraph
with girth more than g and chromatic number at least k. This completes the proof of
Theorem 1.6.
ORCID iDs
Bojan Mohar https://orcid.org/0000-0002-7408-6148
Hehui Wu https://orcid.org/0000-0001-9849-9097
References
[1] N. Alon and J. H. Spencer, The Probabilistic Method, Wiley Series in Discrete Mathematics
and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 4th edition, 2016.
[2] B. Bollobás and N. Sauer, Uniquely colourable graphs with large girth, Canadian J. Math.
28 (1976), 1340–1344, doi:10.4153/cjm-1976-133-5, https://doi.org/10.4153/
cjm-1976-133-5.
[3] P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38, doi:10.4153/
cjm-1959-003-9, https://doi.org/10.4153/cjm-1959-003-9.
[4] P. Erdős, Problems and results in combinatorial analysis and graph theory, in: Proof Techniques
in Graph Theory, Academic Press, New York, pp. 27–35, 1969.
[5] C. Godsil and G. Royle, Algebraic graph theory, Springer-Verlag, New York, 2001, doi:10.
1007/978-1-4613-0163-9, https://doi.org/10.1007/978-1-4613-0163-9.
[6] A. Harutyunyan, P. M. Kayll, B. Mohar and L. Rafferty, Uniquely D-colourable digraphs with
large girth, Canad. J. Math. 64 (2012), 1310–1328, doi:10.4153/cjm-2011-084-9, https:
//doi.org/10.4153/cjm-2011-084-9.
[7] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Comb. Theory Ser. A
25 (1978), 319–324, doi:10.1016/0097-3165(78)90022-5, https://doi.org/10.1016/
0097-3165(78)90022-5.
[8] B. Mohar and H. Wu, Dichromatic number and fractional chromatic number, Forum Math.
Sigma 4 (2016), Paper No. e32, 14, doi:10.1017/fms.2016.28, https://doi.org/10.
1017/fms.2016.28.
[9] B. Mohar and H. Wu, Triangle-free subgraphs with large fractional chromatic number, Combin.
Probab. Comput. 31 (2022), 136–143, doi:10.1017/s0963548321000250, https://doi.
org/10.1017/s0963548321000250.
[10] V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Am. Math. Soc. 64
(1977), 370–371, doi:10.2307/2041460, https://doi.org/10.2307/2041460.
[11] X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory 23 (1996), 33–41, doi:
10.1002/(SICI)1097-0118(199609)23:1⟨33::AID-JGT3⟩3.3.CO;2-P, https://doi.org/
10.1002/(SICI)1097-0118(199609)23:1<33::AID-JGT3>3.3.CO;2-P.