## Abstract

A K_{l}-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 K_{l}-expansion then its chromatic number is O (l sqrt(log l)). In doing so, we obtain a characterization of graphs which contain no odd K_{l}-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 language | English (US) |
---|---|

Pages (from-to) | 20-29 |

Number of pages | 10 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 99 |

Issue number | 1 |

DOIs | |

State | Published - 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