An upper bound on the fractional chromatic number of triangle-free subcubic graphs

Chun Hung Liu

Research output: Contribution to journalArticle

1 Scopus citations

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 χ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 χf (G) ≤ 3 - 3/64 ≈ 2. 953. Lu and Peng improved the bound to χf (G) ≤ 3 - 3/43 ≈ 2.930. Recently, Ferguson, Kaiser, and Král' proved that χf (G) ≤ 32/11 ≈ 2.909. In this paper, we prove that χf (G) ≤ 43/15 ≈ 2.867.

Original languageEnglish (US)
Pages (from-to)1102-1136
Number of pages35
JournalSIAM Journal on Discrete Mathematics
Volume28
Issue number3
DOIs
StatePublished - Jan 1 2014

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Fractional chromatic number
  • Subcubic graphs
  • Triangle-free graphs

Fingerprint Dive into the research topics of 'An upper bound on the fractional chromatic number of triangle-free subcubic graphs'. Together they form a unique fingerprint.

  • Cite this