Skip to Main content Skip to Navigation
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 : Monday, October 12, 2020 - 10:30:17 AM
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, Society for Industrial and Applied Mathematics, 2011, 25 (3), pp.1454-1476. ⟨inria-00635910⟩

Share

Metrics

Record views

363

Files downloads

273