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.
Original language | American English |
---|---|
Pages (from-to) | 5-12 |
Number of pages | 8 |
Journal | Journal of Graph Theory |
Volume | 90 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2019 |
ASJC Scopus subject areas
- Geometry and Topology
Keywords
- Hadwiger's conjecture
- chordal partition
- graph
- minor
- partition