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.
Type de document :
Article dans une revue
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>
Liste complète des métadonnées


https://hal.inria.fr/inria-00635910
Contributeur : František Kardoš <>
Soumis le : mercredi 9 novembre 2011 - 13:49:58
Dernière modification le : jeudi 27 mars 2014 - 10:59:52
Document(s) archivé(s) le : jeudi 30 mars 2017 - 18:13:15

Fichier

KKV11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

118

Téléchargements du document

84