Coloring square-free Berge graphs

Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon, Kristina Vušković

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We consider the class of Berge graphs that do not contain an induced cycle of length four. We present a purely graph-theoretical algorithm that produces an optimal coloring in polynomial time for every graph in that class.

Original languageEnglish (US)
Pages (from-to)96-128
Number of pages33
JournalJournal of Combinatorial Theory. Series B
StatePublished - Mar 2019

All Science Journal Classification (ASJC) codes

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


  • Algorithm
  • Berge graph
  • Coloring
  • Square-free


Dive into the research topics of 'Coloring square-free Berge graphs'. Together they form a unique fingerprint.

Cite this