Thresholds for classes of intersection graphs

DOI10.1016/0012-365X(92)90684-8zbMath0769.05084MaRDI QIDQ1201264

Jan Kratochvíl, Svante Janson

Publication date: 17 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

random graphintersection graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80)

Related Items

MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS ⋮ Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ On the structure of certain intersection graphs ⋮ Covering and coloring polygon-circle graphs ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Induced matchings in intersection graphs. ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ 3D-interval-filament graphs ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Independent packings in structured graphs ⋮ Algorithms for maximum weight induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Poisson convergence and Poisson processes with applications to random graphs
• String graphs. II: Recognizing string graphs is NP-hard
• Reducing prime graphs and recognizing circle graphs
• String graphs requiring exponential representations
• Comparability graphs and intersection graphs
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• Intersection representations of graphs by arcs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topology of Thin Film RC Circuits
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• A Characterization of Comparability Graphs and of Interval Graphs