Bad news for chordal partitions |
| |
| Authors: | Alex Scott Paul Seymour David R Wood |
| |
| Institution: | 1. Mathematical Institute, University of Oxford, Oxford, UK;2. Department of Mathematics, Princeton University, New Jersey, USA;3. School of Mathematical Sciences, Monash University, Melbourne, Australia |
| |
| Abstract: | Reed and Seymour 1998] asked whether every graph has a partition into induced connected nonempty bipartite subgraphs such that the quotient graph is chordal. If true, this would have significant ramifications for Hadwiger's Conjecture. We prove that the answer is “no.” In fact, we show that the answer is still “no” for several relaxations of the question. |
| |
| Keywords: | chordal partition graph Hadwiger's conjecture minor partition |
|
|
