The Fractional Chromatic Number of K_ -Free Graphs

DOI10.1137/21M1440037zbMATH Open1525.05160arXiv2107.00916OpenAlexW4387779320MaRDI QIDQ6081802FDOQ6081802

Authors: Xiaolan Hu, Xing Peng 

Publication date: 26 October 2023

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

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$.

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

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

zbMATH Keywords

coloringfractional coloringfractional chromatic number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Fractional DP-chromatic number of planar graphs of large girth
• Title not available (Why is that?)
• 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)