On Vertex Partitions and some Minor-Monotone Parameters

Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2010, 66 (1), pp.49-56
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00808034
Contributeur : Daniel Gonçalves <>
Soumis le : jeudi 4 avril 2013 - 17:14:41
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00808034, version 1

Collections

Citation

Daniel Gonçalves. On Vertex Partitions and some Minor-Monotone Parameters. Journal of Graph Theory, Wiley, 2010, 66 (1), pp.49-56. 〈lirmm-00808034〉

Partager

Métriques

Consultations de la notice

131