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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom