On the odd-minor variant of Hadwiger's conjecture

J.F. Geelen, B. Gerards, B. Reed, P.D. Seymour, A. Vetta

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

35 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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 . 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.
Originele taal-2Engels
Pagina's (van-tot)20-29
Aantal pagina's13
TijdschriftJournal of Combinatorial Theory, Series B
Volume99
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2009

Vingerafdruk

Duik in de onderzoeksthema's van 'On the odd-minor variant of Hadwiger's conjecture'. Samen vormen ze een unieke vingerafdruk.

Citeer dit