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

DOI10.1112/JLMS/JDT085zbMATH Open1295.05103arXiv1301.5296OpenAlexW3098651475MaRDI QIDQ5494396FDOQ5494396

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)

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

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

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

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)

Cites Work

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

Cited In (9)

• Spotting trees with few leaves
• 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
• Large independent sets in subquartic planar graphs
• 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)