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
Liste complète des métadonnées

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00635910
Contributor : František Kardoš <>
Submitted on : Wednesday, November 9, 2011 - 1:49:58 PM
Last modification on : Friday, April 19, 2019 - 11:12:03 AM
Document(s) archivé(s) le : 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. ⟨http://epubs.siam.org/sidma/resource/1/sjdmec/v25/i3/p1454_s1?isAuthorized=no⟩. ⟨inria-00635910⟩

Share

Metrics

Record views

245

Files downloads

121