Premium
On vertex partitions and some minor‐monotone graph parameters
Author(s) -
Gonçalves D.
Publication year - 2011
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.20490
Subject(s) - combinatorics , mathematics , vertex (graph theory) , monotone polygon , discrete mathematics , graph , partition (number theory) , geometry
Abstract We study vertex partitions of graphs according to some minor‐monotone graph parameters. Ding et al. [J Combin Theory Ser B 79(2) (2000), 221–246] proved that some minor‐monotone parameters ρ are such that, any graph G with ρ( G )⩾2 admits a vertex partition into two graphs with parameter ρ at most ρ( G ) − 1. Here we prove that some of these parameters ρ are such that, any graph G with ρ( G )⩾3 admits a vertex partition into three graphs with parameter ρ at most ρ( G ) − 2. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 49‐56, 2010