Bounding the fractional chromatic number of K_-free graphs

DOI10.1137/120882068MaRDI QIDQ2848565zbMATH OpenOpenAlexFDO

Authors Katherine Edwards, Andrew D. King

Publication date 26 September 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringfractional coloringReed's conjecturefractional chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: King, Lu, and Peng recently proved that for $Deltageq4$, any $K_{D}elta$-free graph with maximum degree $Delta$ has fractional chromatic number at most $Delta-frac267$ unless it is isomorphic to $$ or $C_8^2$. Using a different approach we give improved bounds for $Deltageq6$ and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's $omega$, $Delta$, $chi$ conjecture.

Recommendations

• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• On bounding the difference of the maximum degree and the clique number
• Fractional chromatic number, maximum degree, and girth
• Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
• An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs

Cited in

(7)

• The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• scientific article; zbMATH DE number 7641240 (Why is no real title available?)
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• A superlocal version of Reed's conjecture
• Fractional chromatic number, maximum degree, and girth
• Brooks' Theorem and Beyond

This page was built for publication: Bounding the fractional chromatic number of \(K_\Delta\)-free graphs

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