Skip to Main content Skip to Navigation
New interface
Journal articles

Fractional colorings of cubic graphs with large girth

Abstract : We show that every (sub)cubic n-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978, which implies that it contains an independent set of size at least 0.4352n. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00635910
Contributor : František Kardoš Connect in order to contact the contributor
Submitted on : Wednesday, November 9, 2011 - 1:49:58 PM
Last modification on : Thursday, August 4, 2022 - 4:52:40 PM
Long-term archiving on: : Thursday, March 30, 2017 - 6:13:15 PM

File

KKV11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00635910, version 1

Collections

Citation

František Kardoš, Daniel Kráľ, Jan Volec. Fractional colorings of cubic graphs with large girth. SIAM Journal on Discrete Mathematics, 2011, 25 (3), pp.1454-1476. ⟨inria-00635910⟩

Share

Metrics

Record views

141

Files downloads

92