Bad news for chordal partitions
Reed and Seymour [1998] asked whether every graph has a partition into induced connected non-empty 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 an...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Journal article |
| Được phát hành: |
Wiley
2018
|
| Tóm tắt: | Reed and Seymour [1998] asked whether every graph has a partition into induced connected non-empty 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. |
|---|