The structure of bull-free perfect graphs

Maria Chudnovsky, Irena Penev

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

The bull is a graph consisting of a triangle and two vertex-disjoint pendant edges. A graph is called bull-free if no induced subgraph of it is a bull. A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the size of the largest complete subgraph of H. This article describes the structure of all bull-free perfect graphs.

Original languageEnglish (US)
Pages (from-to)1-31
Number of pages31
JournalJournal of Graph Theory
Volume74
Issue number1
DOIs
StatePublished - Sep 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • bull-free graphs
  • perfect graphs
  • structure theorem

Fingerprint Dive into the research topics of 'The structure of bull-free perfect graphs'. Together they form a unique fingerprint.

  • Cite this