On the odd-minor variant of Hadwiger's conjecture - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Theory, Series B Année : 2009

On the odd-minor variant of Hadwiger's conjecture

Résumé

A Kl-expansion consists of l vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-coloured so that the edges of the trees are bichromatic but the edges between trees are monochromatic. We show that, for every l, if a graph contains no odd Kl-expansion then its chromatic number is View the MathML source. In doing so, we obtain a characterization of graphs which contain no odd Kl-expansion which is of independent interest. We also prove that given a graph and a subset S of its vertex set, either there are k vertex-disjoint odd paths with endpoints in S, or there is a set X of at most 2kâˆ'2 vertices such that every odd path with both ends in S contains a vertex in X. Finally, we discuss the algorithmic implications of these results.
Fichier principal
Vignette du fichier
paper.pdf (142.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00795995 , version 1 (07-03-2013)

Identifiants

  • HAL Id : hal-00795995 , version 1

Citer

Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta. On the odd-minor variant of Hadwiger's conjecture. Journal of Combinatorial Theory, Series B, 2009, 99, pp.20―29. ⟨hal-00795995⟩
240 Consultations
122 Téléchargements

Partager

Gmail Facebook X LinkedIn More