Bad News for Chordal Partitions

MaRDI QIDQ5379811zbMATH OpenFDO

Authors David R. Wood, Alex Scott, Paul Seymour

Publication date 14 June 2019

Full work available at URL https://arxiv.org/abs/1707.04964

zbMATH Keywords

chordal partitiongraphHadwiger's conjectureminorpartition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

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.

Recommendations

• Obstructions to partitions of chordal graphs
• Partitioning chordal graphs
• scientific article; zbMATH DE number 617574
• Vertex partitions of chordal graphs
• Clique Partitions of Chordal Graphs
• scientific article; zbMATH DE number 1047750
• Well-partitioned chordal graphs
• Some New Results on Partitions
• Problems on chain partitions
• The Partitionability Conjecture

Cited in

(1)

• Product structure of graph classes with bounded treewidth

This page was built for publication: Bad News for Chordal Partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5379811)