Three-colourable perfect graphs without even pairs

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

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
Volume102
Issue number2
DOIs
StatePublished - Mar 1 2012

All Science Journal Classification (ASJC) codes

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

Keywords

  • 2-Join
  • Berge graphs
  • Perfect graphs

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

  • Cite this