The structure of bull-free graphs II and III-A summary

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

The bull is a graph consisting of a triangle and two pendant edges. A graph is called bull-free if no induced subgraph of it is a bull. This is a summary of the last two papers [2,3] in a series [1-3] (Chudnovsky, 2012). The goal of the series is to give a complete description of all bull-free graphs. We call a bull-free graph elementary if it does not contain an induced three-edge-path P such that some vertex c∉ V(P) is complete to V(P), and some vertex a∉ V(P) is anticomplete to V(P). Here we prove that every elementary graph either belongs to one of a few basic classes, or admits a certain decomposition, and then uses this result together with the results of [1] (this issue) to give an explicit description of the structure of all bull-free graphs.

Original languageEnglish (US)
Pages (from-to)252-282
Number of pages31
JournalJournal of Combinatorial Theory. Series B
Volume102
Issue number1
DOIs
StatePublished - Jan 2012

All Science Journal Classification (ASJC) codes

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

Keywords

  • Bull-free graphs
  • Graph structure
  • Induced subgraph

Fingerprint Dive into the research topics of 'The structure of bull-free graphs II and III-A summary'. Together they form a unique fingerprint.

Cite this