An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs

DOI10.1137/120900678zbMATH Open1305.05080arXiv1211.4229OpenAlexW2006668015MaRDI QIDQ2935261FDOQ2935261

Authors: Chun-Hung Liu 

Publication date: 22 December 2014

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

Abstract: An $(a:b)$-coloring of a graph $G$ is a function $f$ which maps the vertices of $G$ into $b$-element subsets of some set of size $a$ in such a way that $f(u)$ is disjoint from $f(v)$ for every two adjacent vertices $u$ and $v$ in $G$. The fractional chromatic number $ch{i}_f(G)$ is the infimum of $a/b$ over all pairs of positive integers $a,b$ such that $G$ has an $(a:b)$-coloring. Heckman and Thomas conjectured that the fractional chromatic number of every triangle-free graph $G$ of maximum degree at most three is at most 2.8. Hatami and Zhu proved that $ch{i}_f(G)leq3-3/64approx2.953$. Lu and Peng improved the bound to $ch{i}_f(G)leq3-3/43approx2.930$. Recently, Ferguson, Kaiser and Kr'{a}l' proved that $ch{i}_f(G)leq32/11approx2.909$. In this paper, we prove that $ch{i}_f(G)leq43/15approx2.867$.

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

Recommendations

• On the uniqueness for the heat equation on complete Riemannian manifolds
• Uniqueness of Solutions of a Class of Quasilinear Subelliptic Equations
• Sobolev, Poincaré, and isoperimetric inequalities for subelliptic diffusion operators satisfying a generalized curvature dimension inequality
• Uniqueness properties of diffusion processes
• A note on a poincaré type inequality for solutions to subelliptic equations

zbMATH Keywords

triangle-free graphssubcubic graphsfractional chromatic number

Mathematics Subject Classification ID

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

Cited In (7)

• Bounding the fractional chromatic number of \(K_\Delta\)-free graphs
• The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• Spotting Trees with Few Leaves
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• The fractional chromatic number of graphs of maximum degree at most three
• The fractional chromatic number of triangle-free subcubic graphs

This page was built for publication: An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs

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