Bad news for chordal partitions

Alex Scott, Paul Seymour, David R. Wood

Research output: Contribution to journalArticlepeer-review

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

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Hadwiger's conjecture
  • chordal partition
  • graph
  • minor
  • partition

Fingerprint Dive into the research topics of 'Bad news for chordal partitions'. Together they form a unique fingerprint.

Cite this