Journal article icon

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
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1002/jgt.22363

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
Office for Nuclear Regulation More from this funder
National Science Foundation More from this funder
Australian Research Council More from this funder
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
Pubs id:
pubs:833232
URN:
uri:ad8cf45a-a657-46e7-800e-c096c110226b
UUID:
uuid:ad8cf45a-a657-46e7-800e-c096c110226b
Local pid:
pubs:833232

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP