Fractional chromatic number, maximum degree, and girth

DOI10.1137/20M1382283MaRDI QIDQ5013575zbMATH OpenOpenAlexFDO

Authors François Pirot, Jean-Sébastien Sereni

Publication date 1 December 2021

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

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

zbMATH Keywords

fractional coloringgirthRamsey theorytriangle-free

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10)

Abstract: We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree~$Deltage3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of~$Delta$, and improves it when~$Deltage17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of~$Delta$, we also demonstrate that every graph of girth at least~$7$ and maximum degree~$Delta$ has fractional chromatic number at most~$1+mi{n}_{kinmathbbN}frac2Delta+2^{k-3}k$. In particular, the fractional chromatic number of a graph of girth~$7$ and maximum degree~$Delta$ is at most~$frac2Delta+95$ when~$Deltain[3,8]$, at most~$fracDelta+73$ when~$Deltain[8,20]$, at most~$frac2Delta+237$ when~$Deltain[20,48]$, and at most~$fracDelta4+5$ when~$Deltain[48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree~$Deltain3,4,5$ and girth~$gin6,dotsc,12$, notably~$1/3$ when~$(Delta,g)=(4,10)$ and~$2/7$ when~$(Delta,g)=(5,8)$.

Recommendations

• The fractional chromatic number of graphs of maximum degree at most three
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• Occupancy fraction, fractional colouring, and triangle fraction
• Bounding the fractional chromatic number of K_-free graphs
• Fractional colorings of cubic graphs with large girth

Cites work

• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Coloring triangle-free graphs with local list sizes
• Constructions for cubic graphs with large girth
• Dynamic cage survey
• Fractional colorings of cubic graphs with large girth
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 1151823 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Independence in graphs with maximum degree four
• Large independent sets in triangle-free cubic graphs: beyond planarity
• Local algorithms, regular graphs of large girth, and random regular graphs
• Some Ramsey-Type Numbers and the Independence Ratio
• Some remarks on the theory of graphs
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• The Independence Ratio of Regular Graphs
• The list chromatic number of graphs with small clique number
• The strong perfect graph theorem

Cited in

(7)

• Bounding the fractional chromatic number of K_-free graphs
• The fractional chromatic number of graphs of maximum degree at most three
• Girth and fractional chromatic number of planar graphs
• Occupancy fraction, fractional colouring, and triangle fraction
• 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
• Random independent sets in triangle-free graphs

This page was built for publication: Fractional chromatic number, maximum degree, and girth

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