2017/03/24 by Thomas Schweser, Schweser, Thomas, Michael Stiebitz +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1703.08502
openalex publication_date 2017/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1996, Michael Stiebitz proved that if G is a simple graph with δ(G)≥ s+t+1 and s,t∈ ℤ≥ 0, then V(G) can be partitioned into two sets A and B such that δ(G[A])≥ s and δ(G[B])≥ t. In 2016, Amir Ban proved a similar result for weighted graphs. Let G be a simple graph with at least two vertices, let w:E(G) → \mathbbr>0 be a weight function, let s,t ∈ ℝ≥ 0, and let W=maxe∈ E(G) w(e). If δ(G)≥ s+t+2W, then V(G) can be partitioned into two sets A and B such that δ(G[A])≥ s and δ(G[B])≥ t. This motivated us to consider this partition problem for multigraphs, or equivalently for weighted graphs (G,w) with w:E(G) → ℤ≥ 1. We prove that if s,t∈ \mathbbz≥ 0 and δ(G)≥ s+t+2W-1≥ 1, then V(G) can be partitioned into two sets A and B such that δ(G[A])≥ s and δ(G[B])≥ t. We also prove a variable version of this result and show that for K4--free graphs, the bound on the minimum degree can be decreased.