Premium
Destroying Noncomplete Regular Components in Graph Partitions
Author(s) -
Rabern Landon
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21634
Subject(s) - combinatorics , mathematics , regular graph , edge transitive graph , graph , discrete mathematics , vertex (graph theory) , distance regular graph , disjoint sets , graph power , line graph
We prove that if G is a graph andr 1 , . . . , r k ∈ Z ≥ 0such that∑ i = 1 k r i ≥ Δ ( G ) + 2 − k then V ( G ) can be partitioned into setsV 1 , . . . , V ksuch that Δ ( G [ V i ] ) ≤ r iand G [ V i ] contains no noncomplete r i ‐regular components for each 1 ≤ i ≤ k . In particular, the vertex set of any graph G can be partitioned into ⌈ Δ ( G ) + 2 3 ⌉ sets, each of which induces a disjoint union of triangles and paths.