Excluding induced subgraphs: Critical graphs

József Balogh, Jane Butterfield

Research output: Contribution to journalArticle

Abstract

Determining the cardinality and describing the structure of H-free graphs is well-investigated for many graphs H. In the nineties, Prömel and Steger proved that for a graph H with chromatic number k + 1 almost all graphs not containing H as a subgraph are k-colorable if and only if H contains a color-critical edge. We strengthen the concept of H-free to induced subgraph containment, proving that if H has coloring number k + 1 then almost all H-free graphs can be covered by k graphs that are cliques or independent sets if and only if H is in some well-defined sense critical. The family of critical graphs includes C4 and C2k+1 for all k ≥ 3.

Original languageEnglish (US)
Pages (from-to)100-120
Number of pages21
JournalRandom Structures and Algorithms
Volume38
Issue number1-2
DOIs
StatePublished - Jan 2011

Keywords

  • Critical graphs
  • Extremal graphs
  • Graph counting
  • Structure of H-freegraphs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Excluding induced subgraphs: Critical graphs'. Together they form a unique fingerprint.

  • Cite this