Almost all Berge Graphs are Perfect

DOI10.1017/S0963548300000079zbMath0793.05063OpenAlexW2137272630MaRDI QIDQ4291185

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

perfect graphssplit graphsBerge graphsstrong perfect graph

Mathematics Subject Classification ID

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

Related Items (19)

Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 ⋮ Perfect Graphs of Fixed Density: Counting and Homogeneous Sets ⋮ 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 ⋮ The normal graph conjecture for two classes of sparse graphs ⋮ Random perfect graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Recognition of unipolar and generalised split graphs ⋮ Forbidding induced even cycles in a graph: typical structure and counting ⋮ Perfectly orderable graphs and almost all perfect graphs are kernel \(M\)- solvable ⋮ Unnamed Item ⋮ The first order convergence law fails for random perfect graphs ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable ⋮ Excluding induced subgraphs: Critical graphs ⋮ Algorithms for unipolar and generalized split graphs ⋮ Stability‐type results for hereditary properties ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ The number of 2-SAT functions

Cites Work

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

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