Bad news for chordal partitions
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 12, 2018
- Source ID
- 10.1002/jgt.22363
Entities
People
- Alexander David Scott
- David Wood
- Paul Seymour
Organizations
- Australian Research Council
- Monash University
- National Science Foundation
- Office of Naval Research
- Princeton University
- University of Oxford