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

DOI10.37236/9455zbMath1486.05049arXiv1909.10701OpenAlexW2976124033MaRDI QIDQ2121792

Marcin Smulewicz, Wojciech Nadara

Publication date: 4 April 2022

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

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

zbMATH Keywords

reconfiguration graphssparse graph classes

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposing a graph into pseudoforests with one having bounded degree
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Decomposing a planar graph with girth 9 into a forest and a matching
• Partitioning graphs of bounded tree-width
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Maximum average degree and relaxed coloring
• A polynomial version of Cereceda's conjecture
• The pseudoforest analogue for the strong nine dragon tree conjecture is true
• Reconfiguring colorings of graphs with bounded maximum average degree
• On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
• On the vertex-arboricity of planar graphs
• Defective 2-colorings of sparse graphs
• The point-arboricity of a graph
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
• Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
• On the linear vertex-arboricity of a planar graph
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Partitioning a Planar Graph of Girth 10 into a Forest and a Matching
• Optimal Vertex Partitions
• Edge-partitions of planar graphs and their game coloring numbers
• Vertex Partitions into an Independent Set and a Forest with Each Component Small
• Toward Cereceda's conjecture for planar graphs
• Minimal reducible bounds for the class of \(k\)-degenerate graphs