I,F-partitions of sparse graphs

DOI10.1016/J.EJC.2016.03.003zbMATH Open1339.05300arXiv1510.03381OpenAlexW2963476037MaRDI QIDQ298327FDOQ298327

Authors: Axel Brandt, Michael Ferrara, M. Kumbhat, Sarah Loeb, Derrick Stolee, Matthew Yancey 

Publication date: 20 June 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A star $k$-coloring is a proper $k$-coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $frac52$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219].

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

Recommendations

• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• Star coloring of sparse graphs
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• On star 5-colorings of sparse graphs
• Star coloring high girth planar graphs

zbMATH Keywords

dischargingpotential functionsstar \(k\)-coloring

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• On acyclic colorings of planar graphs
• Colorings of plane graphs: a survey
• Title not available (Why is that?)
• Acyclic colorings of planar graphs
• Coloring with no 2-colored \(P_4\)'s
• Star coloring high girth planar graphs
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Star coloring planar graphs from small lists
• Star coloring bipartite planar graphs
• Star coloring of sparse graphs
• On 1-improper 2-coloring of sparse graphs
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true

Cited In (4)

• On star 5-colorings of sparse graphs
• Additive list coloring of planar graphs with given girth
• Planar graphs with girth 20 are additively 3-choosable
• An introduction to the discharging method via graph coloring

This page was built for publication: I,F-partitions of sparse graphs

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