Destroying Non-Complete Regular Components in Graph Partitions

2011/02/06 by Landon Rabern, Rabern, Landon
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1102.1169

openalex publication_date 2011/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that if G is a graph and r₁, ..., r_k ∈ ℤ_{≥ 0} such that ∑_i=1^k r_i ≥ Δ(G) + 2 - k then V(G) can be partitioned into sets V₁, ..., V_k such that Δ(G[V_i]) ≤ r_i and G[V_i] contains no non-complete r_i-regular components for each 1 ≤ i ≤ k. In particular, the vertex set of any graph G can be partitioned into \lceil (Δ(G) + 2)/(3) \rceil sets, each of which induces a disjoint union of triangles and paths.

Related

• Matchings in regular graphs: minimizing the partition function
• Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph
• Packing subdivisions into regular graphs
• A note on vertex partitions
• New Invariants for Partitioning a Graph into 2-connected Subgraphs