Journal article
Bad news for chordal partitions
- Abstract:
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Office for Nuclear Regulation
More from this funder
Australian Research Council
More from this funder
National Science Foundation
More from this funder
Bibliographic Details
- Publisher:
- Wiley Publisher's website
- Journal:
- Journal of Graph Theory Journal website
- Volume:
- 90
- Issue:
- 5
- Pages:
- 5-12
- Publication date:
- 2018-06-12
- Acceptance date:
- 2018-03-31
- DOI:
- EISSN:
-
1097-0118
- ISSN:
-
0364-9024
- Source identifiers:
-
833232
Item Description
- Pubs id:
-
pubs:833232
- UUID:
-
uuid:ad8cf45a-a657-46e7-800e-c096c110226b
- Local pid:
- pubs:833232
- Deposit date:
- 2018-04-04
Terms of use
- Copyright holder:
- Wiley Periodicals Inc
- Copyright date:
- 2018
- Notes:
- © 2018 Wiley Periodicals, Inc. This is the accepted manuscript version of the article. The final version is available online from Wiley at: https://doi.org/10.1002/jgt.22363
If you are the owner of this record, you can report an update to it here: Report update to this record