The Fractional Chromatic Number of K_ -Free Graphs

DOI10.1137/21M1440037MaRDI QIDQ6081802zbMATH OpenOpenAlexFDO

Authors Xiaolan Hu, Xing Peng

Publication date 26 October 2023

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

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

zbMATH Keywords

coloringfractional coloringfractional chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Fractional graph theory, fuzzy graph theory (05C72)

Abstract: For a simple graph $G$, let $ch{i}_f(G)$ be the fractional chromatic number of $G$. In this paper, we aim to establish upper bounds on $ch{i}_f(G)$ for those graphs $G$ with restrictions on the clique number. Namely, we prove that for $Deltageq4$, if $G$ has maximum degree at most $Delta$ and is $K_{Delta}$-free, then $ch{i}_f(G)leqDelta-frac18$ unless $G=C_8^2$ or $$. This im proves the result in [King, Lu, and Peng, SIAM J. Discrete Math., 26(2) (2012), pp. 452-471] for $Deltageq4$ and the result in [Katherine and King, SIAM J.Discrete Math., 27(2) (2013), pp. 1184-1208] for $Deltain6,7,8$.

Recommendations

• Bounding the fractional chromatic number of \(K_\Delta\)-free graphs
• The fractional chromatic number of graphs of maximum degree at most three
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• Fractional chromatic number, maximum degree, and girth
• The list chromatic number of graphs with small clique number

Cites work

• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• A fractional analogue of Brooks' theorem
• A new proof of the independence ratio of triangle-free cubic graphs
• A strengthening of Brooks' theorem
• An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs
• Bounding the fractional chromatic number of \(K_\Delta\)-free graphs
• Edge density and independence ratio in triangle-free graphs with maximum degree three
• Fractional colorings of cubic graphs with large girth
• Graph colouring and the probabilistic method
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Some Ramsey-Type Numbers and the Independence Ratio
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• The fractional chromatic number of graphs of maximum degree at most three
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• The fractional chromatic number of triangle-free subcubic graphs

Cited in

(3)

• Fractional DP-chromatic number of planar graphs of large girth
• scientific article; zbMATH DE number 7407404 (Why is no real title available?)
• On (k,d)-colorings and fractional nowhere-zero flows

This page was built for publication: The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs

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