Triangle-free subgraphs with large fractional chromatic number

DOI10.1016/J.ENDM.2015.06.089zbMATH Open1346.05079arXiv1808.01605OpenAlexW2201158599MaRDI QIDQ322348FDOQ322348

Bojan Mohar, Hehui Wu

Publication date: 14 October 2016

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.

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

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\)

zbMATH Keywords

chromatic numberfractional chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Uniquely Colourable Graphs with Large Girth
• On the Chromatic Number of Subgraphs of a Given Graph
• Title not available (Why is that?)

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)