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
*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/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 6 (2023) #P2.11
https://doi.org/10.26493/2590-9770.1491.14a
(Dostopno tudi na http://adam-journal.eu)
Podgrafi Kneserjevih grafov z veliko ožino in
velikim kromatskim številom
Bojan Mohar*
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
Hehui Wu†
Shanghai Center for Math. Sci., Fudan University, Shanghai, China
Prejeto 13. oktobra 2021, sprejeto 18. oktobra 2022, objavljeno na spletu 9. decembra 2022
Povzetek
Dobro znano je, da za poljubni celi števili k in g obstaja graf s kromatskim številom
najmanj k in ožino najmanj g. V 1960-ih sta Erdős in Hajnal postavila domnevo, da za
poljubni števili k in g obstaja tako število h(k, g), da vsak graf, katerega kromatsko število
je najmanj h(k, g), vsebuje podgraf, katerega kromatsko število je najmanj k, ožina pa
najmanj g. Erdős-Hajnalova domneva je bila nedavno na novo formulirana s pojmi frak-
cijskega kromatskega števila. V podporo izvirni in modificirani domnevi dokažemo, da
vsak Kneserjev graf, katerega (frakcijsko) kromatsko število je dovolj veliko, vsebuje pod-
graf velike ožine, katerega (frakcijsko) kromatsko število je veliko.
Ključne besede: Kneserjev graf, barvanje grafov, kromatsko število, frakcijsko kromatsko število.
Math. Subj. Class.: 05C15
*Kontaktni avtor. Delno podprt s strani raziskovalne štipendije NSERC R611450 (Kanada), s strani Canada
Research Chairs programa, in v okviru raziskovalnega projekta J1-2452 agencije ARRS (Slovenija). IMFM,
Jadranska 19, 1000 Ljubljana.
†Del te raziskave je bil opravljen, ko je bil avtor podoktorski študent PIMS na Department of Mathematics,
Simon Fraser University, Burnaby, B.C.
E-poštna naslova: mohar@sfu.ca (Bojan Mohar), hhwu@fudan.edu.cn (Hehui Wu)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/