Three-colourable perfect graphs without even pairs

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We still do not know how to construct the "most general" perfect graph, not even the most general three-colourable perfect graph. But constructing all perfect graphs with no even pairs seems easier, and here we make a start on it; we construct all three-connected three-colourable perfect graphs without even pairs and without clique cutsets. They are all either line graphs of bipartite graphs, or complements of such graphs.

Original languageEnglish (US)
Pages (from-to)363-394
Number of pages32
JournalJournal of Combinatorial Theory. Series B
Issue number2
StatePublished - Mar 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • 2-Join
  • Berge graphs
  • Perfect graphs


Dive into the research topics of 'Three-colourable perfect graphs without even pairs'. Together they form a unique fingerprint.

Cite this