On the odd-minor variant of Hadwiger's conjecture

Jim Geelen 1 Bert Gerards 1 Bruce Reed Paul Seymour 1 Adrian Vetta 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2009, 99, pp.20―29
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

Contributeur : Alain Monteil <>
Soumis le : jeudi 7 mars 2013 - 11:22:20
Dernière modification le : jeudi 7 février 2019 - 14:24:45
Document(s) archivé(s) le : dimanche 2 avril 2017 - 07:28:16


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00795995, version 1



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, Elsevier, 2009, 99, pp.20―29. 〈hal-00795995〉



Consultations de la notice


Téléchargements de fichiers