Graph partitions under average degree constraint

DOI10.1016/J.JCTB.2023.11.006MaRDI QIDQ6187347zbMATH OpenOpenAlexFDO

Authors Yan Wang, Hehui Wu

Publication date 15 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

average degreebalanced partitionvertex partition

Mathematics Subject Classification ID

Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: In this paper, we prove that every graph with average degree at least $s+t+2$ has a vertex partition into two parts, such that one part has average degree at least $s$, and the other part has average degree at least $t$. This solves a conjecture of Cs'{o}ka, Lo, Norin, Wu and Yepremyan.

Recommendations

• Partitions of graphs with high minimum degree or connectivity.
• On partitions of graphs under degree constraints
• Partitioning graphs with linear minimum degree
• A note on partitions of graphs under degree constraints
• Partitions of graphs and multigraphs under degree constraints

Cites work

• A note on defective colorings of graphs in surfaces
• Algorithmic approach to the satisfactory graph partitioning problem
• Asymptotic density of graphs excluding disconnected minors
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
• Decomposing C₄-free graphs under degree constraints
• Decomposing graphs with girth at least five under degree constraints
• Decomposing weighted graphs
• Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
• Defective 2-colorings of sparse graphs
• Defective coloring on classes of perfect graphs
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Efficient algorithms for decomposing graphs under degree constraints
• Extremal results on defective colorings of graphs
• Graph decomposition with constraints on the connectivity and minimum degree
• scientific article; zbMATH DE number 1933255 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 2104729 (Why is no real title available?)
• scientific article; zbMATH DE number 3228454 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• Improper coloring of graphs on surfaces
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• Improper coloring of sparse graphs with a given girth. II: Constructions
• Improper coloring of unit disk graphs
• Internal partitions of regular graphs
• New restrictions on defective coloring with applications to Steinberg-type graphs
• Note on improper coloring of 1-planar graphs.
• On 1-improper 2-coloring of sparse graphs
• On a conjecture of Schweser and Stiebitz
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• On connected partition with degree constraints
• On decomposition of triangle-free graphs under degree constraints
• On partitions of \(K_{2, 3}\)-free graphs under degree constraints
• On partitions of graphs under degree constraints
• Parameterized (approximate) defective coloring
• Partitions of graphs and multigraphs under degree constraints
• Partitions of multigraphs under minimum degree constraints
• Problems and results on judicious partitions
• The extremal function for disconnected minors
• The number of defective colorings of graphs on surfaces

This page was built for publication: Graph partitions under average degree constraint

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