We show that every planar graph G has a 2-fold 9-coloring. In particular, this implies that G has fractional chromatic number at most 92. This is the first proof (independent of the 4 Color Theorem) that there exists a constant k<5 such that every planar G has fractional chromatic number at most k. We also show that every n-vertex planar graph has an independent set of size at least 3n13. This improves on Albertson's bound of 2n9.
%0 Unpublished Work
%1 cranston15
%A Cranston, Daniel W.
%A Rabern, Landon
%D 2015
%K graph.theory planar
%T Planar Graphs are $9/2$-Colorable and Have Independence Ratio at Least $3/13$
%U http://arxiv.org/abs/1410.7233
%X We show that every planar graph G has a 2-fold 9-coloring. In particular, this implies that G has fractional chromatic number at most 92. This is the first proof (independent of the 4 Color Theorem) that there exists a constant k<5 such that every planar G has fractional chromatic number at most k. We also show that every n-vertex planar graph has an independent set of size at least 3n13. This improves on Albertson's bound of 2n9.
@unpublished{cranston15,
abstract = {We show that every planar graph G has a 2-fold 9-coloring. In particular, this implies that G has fractional chromatic number at most 92. This is the first proof (independent of the 4 Color Theorem) that there exists a constant k<5 such that every planar G has fractional chromatic number at most k. We also show that every n-vertex planar graph has an independent set of size at least 3n13. This improves on Albertson's bound of 2n9.},
added-at = {2015-11-06T08:14:38.000+0100},
author = {Cranston, Daniel W. and Rabern, Landon},
biburl = {https://www.bibsonomy.org/bibtex/2b42dc512f8fcef4f8cd04264b31106b7/ytyoun},
interhash = {2e4d5fc19bf88aba73e73645a54af435},
intrahash = {b42dc512f8fcef4f8cd04264b31106b7},
keywords = {graph.theory planar},
timestamp = {2015-11-06T08:14:38.000+0100},
title = {Planar Graphs are $9/2$-Colorable and Have Independence Ratio at Least $3/13$},
url = {http://arxiv.org/abs/1410.7233},
year = 2015
}