Bad news for chordal partitions

Alex Scott, Paul Douglas Seymour, David R. Wood

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)5-12
Number of pages8
JournalJournal of Graph Theory
Volume90
Issue number1
DOIs
StatePublished - Jan 1 2019

Fingerprint

Hadwiger's Conjecture
Quotient Graph
Partition
Ramification
Subgraph
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Cite this

Scott, Alex ; Seymour, Paul Douglas ; Wood, David R. / Bad news for chordal partitions. In: Journal of Graph Theory. 2019 ; Vol. 90, No. 1. pp. 5-12.
@article{20bfbdd2c03d40f6906b482fe5059677,
title = "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.",
author = "Alex Scott and Seymour, {Paul Douglas} and Wood, {David R.}",
year = "2019",
month = "1",
day = "1",
doi = "https://doi.org/10.1002/jgt.22363",
language = "English (US)",
volume = "90",
pages = "5--12",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "1",

}

Bad news for chordal partitions. / Scott, Alex; Seymour, Paul Douglas; Wood, David R.

In: Journal of Graph Theory, Vol. 90, No. 1, 01.01.2019, p. 5-12.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Bad news for chordal partitions

AU - Scott, Alex

AU - Seymour, Paul Douglas

AU - Wood, David R.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85056389727&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056389727&partnerID=8YFLogxK

U2 - https://doi.org/10.1002/jgt.22363

DO - https://doi.org/10.1002/jgt.22363

M3 - Article

VL - 90

SP - 5

EP - 12

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -