Subcubic triangle-free graphs have fractional chromatic number at most 14/5

DOI10.1112/JLMS/JDT085MaRDI QIDQ5494396zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec

Publication date 28 July 2014

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Erdős-Vizing conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Fractional graph theory, fuzzy graph theory (05C72)

Abstract: We prove that every subcubic triangle-free graph has fractional chromatic number at most 14/5, thus confirming a conjecture of Heckman and Thomas [A new proof of the independence ratio of triangle-free cubic graphs. Discrete Math. 233 (2001), 233--237].

Recommendations

• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• The fractional chromatic number of triangle-free subcubic graphs
• An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• On the chromatic number of triangle-free graphs of large minimum degree

Cites work

• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 3536160 (Why is no real title available?)
• scientific article; zbMATH DE number 3556125 (Why is no real title available?)
• scientific article; zbMATH DE number 908794 (Why is no real title available?)
• A (<5)-Colour Theorem for Planar Graphs
• A lower bound for the independence number of a planar graph
• A new proof of the independence ratio of triangle-free cubic graphs
• Bipartite subgraphs of triangle-free subcubic graphs
• Every Planar Map is Four Colorable
• Every planar map is four colorable. I: Discharging
• Independence in graphs with maximum degree four
• Independent sets in triangle-free cubic planar graphs
• Planar Ramsey numbers
• Size and independence in triangle‐free graphs with maximum degree three
• Some Ramsey-Type Numbers and the Independence Ratio
• The four-colour theorem
• The fractional chromatic number of graphs of maximum degree at most three
• The fractional chromatic number of mycielski's graphs
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• The fractional chromatic number of triangle-free subcubic graphs

Cited in

(9)

• Spotting trees with few leaves
• The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs
• Large independent sets in subquartic planar graphs
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Triangle-free subgraphs with large fractional chromatic number
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• Fractional chromatic number, maximum degree, and girth
• The fractional chromatic number of triangle-free subcubic graphs
• Brooks' Theorem and Beyond

This page was built for publication: Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)

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