Fractional coloring of planar graphs of girth five

DOI10.1137/18M1214068MaRDI QIDQ5217825zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Xiaolan Hu

Publication date 26 February 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.05439

zbMATH Keywords

fractional coloringgirthplanar graphtriangle-free

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: A graph G is (a:b)-colorable if there exists an assignment of b-element subsets of {1,...,a} to vertices of G such that sets assigned to adjacent vertices are disjoint. We first show that for every triangle-free planar graph G and a vertex x of G, the graph G has a set coloring phi by subsets of {1,...,6} such that |phi(v)|>=2 for each vertex v of G and |phi(x)|=3. As a corollary, every triangle-free planar graph on n vertices is (6n:2n+1)-colorable. We further use this result to prove that for every Delta, there exists a constant M_Delta such that every planar graph G of girth at least five and maximum degree Delta is (6M_Delta:2M_Delta+1)-colorable. Consequently, planar graphs of girth at least five with bounded maximum degree Delta have fractional chromatic number at most 3-3/(2M_Delta+1).

Recommendations

• Every planar graph with girth at least 5 is (1,9)-colorable
• Planar graphs with girth at least 5 are (3, 5)-colorable
• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• Girth and fractional chromatic number of planar graphs
• Planar graphs without 4- and 6-cycles are (7 : 2)-colorable

Cites work

• \((3a:a)\)-list-colorability of embedded graphs of girth at least five
• Fractional coloring of triangle-free planar graphs
• Hyperbolic families and coloring graphs on surfaces
• Independence in graphs with maximum degree four
• Large independent sets in triangle-free planar graphs

Cited in

(9)

• Density of 5/2-critical graphs
• Extending partial 5-colorings and 6-colorings in planar graphs
• Fractional colorings of cubic graphs with large girth
• Girth and fractional chromatic number of planar graphs
• Fractional DP-chromatic number of planar graphs of large girth
• Fractional coloring methods with applications to degenerate graphs and graphs on surfaces
• Contact graphs of boxes with unidirectional contacts
• The independence ratio of 4-cycle-free planar graphs
• Fractional coloring of triangle-free planar graphs

This page was built for publication: Fractional coloring of planar graphs of girth five

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217825)