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...
Príomhchruthaitheoirí: | Scott, A, Seymour, P, Wood, D |
---|---|
Formáid: | Journal article |
Foilsithe / Cruthaithe: |
Wiley
2018
|
Míreanna comhchosúla
-
Graphs of low chordality
de réir: Sunil Chandran, et al.
Foilsithe / Cruthaithe: (2005-01-01) -
Graphs of low chordality
de réir: L. Sunil Chandran, et al.
Foilsithe / Cruthaithe: (2005-12-01) -
Edge erasures and chordal graphs
de réir: Jared Culbertson, et al.
Foilsithe / Cruthaithe: (2021-10-01) -
Chordal Networks of Polynomial Ideals
de réir: Cifuentes, Diego Fernando, et al.
Foilsithe / Cruthaithe: (2019) -
Bad News
de réir: Cecilia Stenbom, et al.
Foilsithe / Cruthaithe: (2023-06-01)