Title: Partitions of multigraphs under minimum degree constraints
Abstract: In 1996, Michael Stiebitz proved that if G is a simple graph with δ ( G ) ≥ s + t + 1 and s , t ∈ Z 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 ) → R > 0 be a weight function, let s , t ∈ R ≥ 0 , and let W = max e ∈ E ( G ) w ( e ) . If δ ( G ) ≥ s + t + 2 W , 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 ) → Z ≥ 1 . We prove that if s , t ∈ Z ≥ 0 and δ ( G ) ≥ s + t + 2 W − 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 K 4 − -free graphs, the bound on the minimum degree can be decreased.