An \((F_3,F_5)\)-partition of planar graphs with girth at least 5
type: Item
instance of: scholarly article
title: An \((F_3,F_5)\)-partition of planar graphs with girth at least 5
author: Min Chen
author: Weiqiang Yu
author: André Raspaud
author: Weifan Wang
published in: Discrete Mathematics
publication date: 2022-11-23T00:00:00Z
review text: For classes of graphs \(\mathcal{C}_1, \mathcal{C}_2,\dots, \mathcal{C}_k\), a \((\mathcal{C}_1, \mathcal{C}_2,\dots, \mathcal{C}_k)\)-partition of a graph \(G\) is a partition \((V_1, V_2,\dots, V_k)\) of \(V(G)\) with \(G[V_i]\in\mathcal{C}_i\) for each \(i\), \(1\le i\le k\). It is a generalization of a traditional vertex-coloring of a graph. Actually, for a non-negative integer \(d\), let \(\Delta_d\) denote the class of graphs of maximum degree at most \(d\). Then a \(k\)-coloring is a \((\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k)\)-partition with \(\mathcal{C}_1 = \mathcal{C}_2 =\dots =\mathcal{C}_k=\Delta_0\). In particular, The Four Color Theorem states that every planar graph admits a \((\Delta_0, \Delta_0, \Delta_0, \Delta_0)\)-partition. \textit{I. Choi} and \textit{A. Raspaud} [ibid. 338, No. 4, 661--667 (2015; Zbl 1305.05072)] proved that every planar graph of girth at least~\(5\) admits a \((\Delta_3, \Delta_5)\)-partition. In this paper, the authors strengthen this result and prove that every planar graph of girth at least~\(5\) admits an \((F_3, F_5)\)-partition, where \(F_d\) is the class of forests of maximum degree at most \(d\).
reviewed by: Akira Saito
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 7622659
zbMATH Keywords: planar graph
zbMATH Keywords: girth
zbMATH Keywords: vertex partition
zbMATH Keywords: forest
MaRDI profile type: Publication
full work available at URL: j.disc.2022.113216
OpenAlex ID: W4307725207
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: Q4137202
cites work: Q4797463
cites work: Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
cites work: Defective 2-colorings of sparse graphs
cites work: (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
cites work: Planar graphs with girth at least 5 are \((3, 4)\)-colorable
cites work: The Point-Arboricity of Planar Graphs
cites work: Planar graphs with girth at least 5 are \((3, 5)\)-colorable
cites work: Vertex-arboricity of planar graphs without intersecting triangles
cites work: On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
cites work: Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
cites work: Improper choosability of graphs and maximum average degree
cites work: Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
cites work: Every planar graph with girth at least 5 is \((1,9)\)-colorable
cites work: Near-colorings: non-colorable graphs and NP-completeness
cites work: On the linear vertex-arboricity of a planar graph
cites work: On the vertex-arboricity of planar graphs
cites work: List improper colorings of planar graphs with prescribed girth
cites work: A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable
DOI: 10.1016/J.DISC.2022.113216
Recommended article: On the vertex partition of planar graphs into forests with bounded degree
Recommended article: Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
Recommended article: Covering planar graphs with forests, one having bounded maximum degree
Recommended article: Covering planar graphs with forests, one having a bounded maximum degree
Recommended article: Planar graphs with girth at least 5 are \((3, 4)\)-colorable
Recommended article: Partitioning sparse graphs into an independent set and a forest of bounded degree
Recommended article: Every planar graph with girth at least 5 is \((1,9)\)-colorable
Recommended article: Decomposing a planar graph of girth 5 into an independent set and a forest
Recommended article: Planar graphs with girth at least 5 are \((3, 5)\)-colorable
description: scientific article; zbMATH DE number 7622659