Almost all Berge Graphs are Perfect

DOI10.1017/S0963548300000079MaRDI QIDQ4291185zbMATH OpenOpenAlexFDO

Authors Hans Jürgen Prömel, Angelika Steger

Publication date 30 May 1994

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300000079

zbMATH Keywords

Berge graphsperfect graphssplit graphsstrong perfect graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Recommendations

• The strong perfect graph theorem
• Publication:3487429
• Progress on perfect graphs
• scientific article; zbMATH DE number 1789914

Cites work

• Asymptotic Enumeration of Partial Orders on a Finite Set
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs: quadrilaterals
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Weakly triangulated graphs

Cited in

(24)

• Bull-free Berge graphs are perfect
• Perfectly orderable graphs and almost all perfect graphs are kernel \(M\)- solvable
• The normal graph conjecture for two classes of sparse graphs
• Recognition of unipolar and generalised split graphs
• Forbidding induced even cycles in a graph: typical structure and counting
• The first order convergence law fails for random perfect graphs
• The number of 2-SAT functions
• Almost all string graphs are intersection graphs of plane convex sets
• Almost perfect matrices and graphs.
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• Induced C₅-free graphs of fixed density: counting and homogeneous sets
• Perfect graphs of fixed density: counting and homogeneous sets
• Excluding induced subgraphs: critical graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Stability-type results for hereditary properties
• scientific article; zbMATH DE number 738898 (Why is no real title available?)
• Random perfect graphs
• Almost all string graphs are intersection graphs of plane convex sets
• Perfectly contractile graphs and quadratic toric rings
• The structure of almost all graphs in a hereditary property
• For most graphs H, most H-free graphs have a linear homogeneous set
• Cover numbers by certain graph families
• Typical structure of hereditary graph families. II: Exotic examples
• Algorithms for unipolar and generalized split graphs

This page was built for publication: Almost all Berge Graphs are Perfect

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4291185)