Fractional colorings of cubic graphs with large girth
Authors:
- František KardošFKFrantišek Kardoš
- Daniel Král’DKDaniel Král’
- Jan VolecJVJan Volec
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 25 (3) , 1454-1476
Abstract
We show that every (sub)cubic [Formula: see text]-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 [Formula: see text]. 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.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- The Fractional Chromatic Number of Graphs of Maximum Degree at Most ThreeSIAM Journal on Discrete Mathematics, 2010
- Large independent sets in random regular graphsTheoretical Computer Science, 2009
- ASPECTS OF STRUCTURAL COMBINATORICS (Graph Homomorphisms and Their Use)Taiwanese Journal of Mathematics, 1999
- Differential Equations for Random Processes and Random GraphsThe Annals of Applied Probability, 1995
- On the independence number of random cubic graphsRandom Structures & Algorithms, 1994
- On the bipartite density of regular graphs with large girthJournal of Graph Theory, 1990
- The asymptotic distribution of short cycles in random regular graphsJournal of Combinatorial Theory, Series B, 1981