I,F-partitions of sparse graphs

DOI10.1016/J.EJC.2016.03.003MaRDI QIDQ298327zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

dischargingpotential functionsstar \(k\)-coloring

Mathematics Subject Classification ID

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

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].

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

Cites work

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

Cited in

(5)

• Additive list coloring of planar graphs with given girth
• Planar graphs with girth 20 are additively 3-choosable
• On star 5-colorings of sparse graphs
• An introduction to the discharging method via graph coloring
• \((\mathcal{F}_1, \mathcal{F})\)-partition of plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles

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)