Bad news for chordal partitions

Alex Scott; Paul Seymour; David R. Wood

doi:10.1002/jgt.22363

Bad news for chordal partitions

Alex Scott, Paul Seymour, David R. Wood

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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	English (US)
Pages (from-to)	5-12
Number of pages	8
Journal	Journal of Graph Theory
Volume	90
Issue number	1
DOIs	https://doi.org/10.1002/jgt.22363
State	Published - Jan 2019

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Hadwiger's conjecture
chordal partition
graph
minor
partition

Access to Document

10.1002/jgt.22363

Cite this

@article{6c32de387c564511bbba44c5230f63b3,

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.",

keywords = "Hadwiger's conjecture, chordal partition, graph, minor, partition",

author = "Alex Scott and Paul Seymour and Wood, {David R.}",

note = "Publisher Copyright: {\textcopyright} 2018 Wiley Periodicals, Inc.",

year = "2019",

month = jan,

doi = "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",

}

TY - JOUR

T1 - Bad news for chordal partitions

AU - Scott, Alex

AU - Seymour, Paul

AU - Wood, David R.

PY - 2019/1

Y1 - 2019/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.

KW - Hadwiger's conjecture

KW - chordal partition

KW - graph

KW - minor

KW - partition

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 - 10.1002/jgt.22363

DO - 10.1002/jgt.22363

M3 - Article

AN - SCOPUS:85056389727

SN - 0364-9024

VL - 90

SP - 5

EP - 12

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Bad news for chordal partitions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this