Triangle-free subgraphs with large fractional chromatic number

DOI10.1016/J.ENDM.2015.06.089MaRDI QIDQ322348zbMATH OpenOpenAlexFDO

Authors Bojan Mohar, Hehui Wu

Publication date 14 October 2016

Full work available at URL https://arxiv.org/abs/1808.01605

zbMATH Keywords

chromatic numberfractional chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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 1960's, ErdH{o}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$. In 1977, R"{o}dl proved the case for $g=4$ and arbitrary $k$. We prove the fractional chromatic number version of R"{o}dl's result.

Recommendations

• Triangle-free subgraphs with large fractional chromatic number
• Subgraphs of Kneser graphs with large girth and large chromatic number
• On the chromatic number of triangle-free graphs of large minimum degree
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)

Cites work

• scientific article; zbMATH DE number 927067 (Why is no real title available?)
• On the Chromatic Number of Subgraphs of a Given Graph
• Uniquely Colourable Graphs with Large Girth

Cited in

(3)

• Subgraphs of Kneser graphs with large girth and large chromatic number
• Triangle-free subgraphs with large fractional chromatic number
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

This page was built for publication: Triangle-free subgraphs with large fractional chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322348)