Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
From MaRDI portal
Publication:2121792
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
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