Partitioning sparse graphs into an independent set and a forest of bounded degree

MaRDI QIDQ1753010zbMATH OpenFDO

Authors François Dross, Alexandre Pinlou, Mickaël Montassier

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.04394, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p45

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

forestsindependent setsplanar graphssparse graphsvertex decompositions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: An $(calI,{calF}_d)$-partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$, such that $I$ is an independent set and $F$ induces a forest of maximum degree at most $d$. We show that for all $M<3$ and $dgefrac23-M-2$, if a graph has maximum average degree less than $M$, then it has an $(calI,{calF}_d)$-partition. Additionally, we prove that for all $frac83leM<3$ and $dgefrac13-M$, if a graph has maximum average degree less than $M$ then it has an $(calI,{calF}_d)$-partition.

Review text

Summary: An \((\mathcal I,\mathcal F_d)\)-partition of a graph is a partition of the vertices of the graph into two sets \(I\) and \(F\), such that \(I\) is an independent set and \(F\) induces a forest of maximum degree at most \(d\). We show that for all \(M<3\) and \(d \geq \frac{2}{3-M} - 2\), if a graph has maximum average degree less than \(M\), then it has an \((\mathcal I,\mathcal F_d)\)-partition. Additionally, we prove that for all \(\frac{8}{3} \leq M < 3\) and \(d \geq \frac{1}{3-M}\), if a graph has maximum average degree less than \(M\) then it has an \((\mathcal I,\mathcal F_d)\)-partition. It follows that planar graphs with girth at least \(7\) (resp. \(8\), \(10\)) admit an \((\mathcal I,\mathcal F_5)\)-partition (resp. \((\mathcal I,\mathcal F_3)\)-partition, \((\mathcal I,\mathcal F_2)\)-partition).

Recommendations

• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• Vertex partitions into an independent set and a forest with each component small
• On the vertex partition of planar graphs into forests with bounded degree

Cites work

• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Brook's theorem
• Coloring Graphs with Constraints on Connectivity
• Colour-critical graphs and hypergraphs
• Grad und lokaler Zusammenhang in endlichen Graphen
• scientific article; zbMATH DE number 3467141 (Why is no real title available?)
• scientific article; zbMATH DE number 866055 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On critical subgraphs of colour-critical graphs
• On the structure of 5- and 6-chromatic abstract graphs.
• The structure of k-chromatic graphs

Cited in

(15)

• An \((F_3,F_5)\)-partition of planar graphs with girth at least 5
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• Fair splittings by independent sets in sparse graphs
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• I,F-partitions of sparse graphs
• Decomposition of sparse graphs into two forests, one having bounded maximum degree
• Vertex partitions into an independent set and a forest with each component small
• Recognizing Graphs Close to Bipartite Graphs
• scientific article; zbMATH DE number 975383 (Why is no real title available?)
• An (F1,F4)‐partition of graphs with low genus and girth at least 6
• Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition
• A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
• Sparse partition universal graphs for graphs of bounded degree
• Planar graphs without \(5^-\)-cycles at distance less than 3 are \((\mathcal{I}, \mathcal{F})\)-colorable

This page was built for publication: Partitioning sparse graphs into an independent set and a forest of bounded degree

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