On the odd-minor variant of Hadwiger's conjecture

Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta

Research output: Contribution to journalArticle

34 Scopus citations

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 O (l sqrt(log l)). 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 2 k - 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.

Original languageEnglish (US)
Pages (from-to)20-29
Number of pages10
JournalJournal of Combinatorial Theory. Series B
Volume99
Issue number1
DOIs
StatePublished - Jan 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Graph colouring
  • Graph minors
  • Hadwiger
  • Jonquil

Fingerprint Dive into the research topics of 'On the odd-minor variant of Hadwiger's conjecture'. Together they form a unique fingerprint.

  • Cite this