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...
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Journal article |
| Gepubliceerd in: |
Wiley
2018
|
| _version_ | 1826290855077478400 |
|---|---|
| author | Scott, A Seymour, P Wood, D |
| author_facet | Scott, A Seymour, P Wood, D |
| author_sort | Scott, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T02:50:35Z |
| format | Journal article |
| id | oxford-uuid:ad8cf45a-a657-46e7-800e-c096c110226b |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:50:35Z |
| publishDate | 2018 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:ad8cf45a-a657-46e7-800e-c096c110226b2022-03-27T03:36:19ZBad news for chordal partitionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:ad8cf45a-a657-46e7-800e-c096c110226bSymplectic Elements at OxfordWiley2018Scott, ASeymour, PWood, DReed 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. |
| spellingShingle | Scott, A Seymour, P Wood, D Bad news for chordal partitions |
| title | Bad news for chordal partitions |
| title_full | Bad news for chordal partitions |
| title_fullStr | Bad news for chordal partitions |
| title_full_unstemmed | Bad news for chordal partitions |
| title_short | Bad news for chordal partitions |
| title_sort | bad news for chordal partitions |
| work_keys_str_mv | AT scotta badnewsforchordalpartitions AT seymourp badnewsforchordalpartitions AT woodd badnewsforchordalpartitions |