Recognition of some perfectly orderable graph classes

DOI10.1016/S0166-218X(02)00499-7zbMath1019.68075MaRDI QIDQ1811119

R. Sritharan, Jeremy P. Spinrad, Elaine M. Eschen, Julie L. Johnson

Publication date: 10 June 2003

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

zbMATH Keywords

perfectly orderable graph; recognition algorithm; brittle graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C75: Structural characterization of families of graphs

Related Items

An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Bipolarizable graphs
• Matrix multiplication via arithmetic progressions
• On the complexity of recognizing perfectly orderable graphs
• Bipartable graphs
• A note on superbrittle graphs
• Generalized neighbourhoods and a class of perfectly orderable graphs
• Welsh-Powell opposition graphs
• Weak bipolarizable graphs
• \(P_ 4\)-comparability graphs
• On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions
• A note on perfect orders
• Modular decomposition and transitive orientation
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• On \(P_4\)-transversals of perfect graphs
• Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam
• On the semi-perfect elimination
• Quasi-brittle graphs, a new class of perfectly orderable graphs
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• On brittle graphs
• Four classes of perfectly orderable graphs
• Some classes of perfectly orderable graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Finding houses and holes in graphs