Vertex Partitions into an Independent Set and a Forest with Each Component Small

DOI10.1137/21M1392280zbMath1470.05131arXiv2006.11445OpenAlexW3191919441MaRDI QIDQ5009333

Daniel W. Cranston, Matthew P. Yancey

Publication date: 20 August 2021

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

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

zbMATH Keywords

coloringpotential methodvertex partitionsparsitymaximum average degree

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph

Cites Work

• On 1-improper 2-coloring of sparse graphs
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• Defective 2-colorings of sparse graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Sparse Graphs Are Near-Bipartite

This page was built for publication: Vertex Partitions into an Independent Set and a Forest with Each Component Small