Which claw-free graphs are perfectly orderable?
From MaRDI portal
Publication:686245
DOI10.1016/0166-218X(93)90221-9zbMath0783.05086MaRDI QIDQ686245
Publication date: 13 March 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
characterizationNP-completeclawperfectly orderableclaw-free graphscomplements of bipartite graphsline- graphsperfect linear order
Structural characterization of families of graphs (05C75) Graph theory (05C99) Ordered structures (06F99)
Related Items (19)
On dart-free perfectly contractile graphs ⋮ Claw-free graphs---a survey ⋮ Path parity and perfection ⋮ Characterization and recognition of some opposition and coalition graph classes ⋮ All variations on perfectly orderable graphs ⋮ A polynomial algorithm for the parity path problem on perfectly orientable graphs ⋮ A note on perfectly orderable graphs ⋮ Even pairs in claw-free perfect graphs ⋮ Strongly perfect claw‐free graphs—A short proof ⋮ On the online track assignment problem ⋮ Which claw-free graphs are strongly perfect? ⋮ Completely separable graphs ⋮ On opposition graphs, coalition graphs, and bipartite permutation graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ A charming class of perfectly orderable graphs ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ Which claw-free graphs are perfectly orderable? ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ The maximum clique problem
Cites Work
- Unnamed Item
- Which claw-free graphs are perfectly orderable?
- On rigid circuit graphs
- Domination, independent domination, and duality in strongly chordal graphs
- On the complexity of recognizing perfectly orderable graphs
- Bipartable graphs
- Recognizing claw-free perfect graphs
- \(P_ 4\)-comparability graphs
- An algorithm for finding clique cut-sets
- Characterizations of totally balanced matrices
- Which line-graphs are perfectly orderable?
- Totally-Balanced and Greedy Matrices
- Doubly Lexical Orderings of Matrices
- On brittle graphs
- Four classes of perfectly orderable graphs
- Some classes of perfectly orderable graphs
This page was built for publication: Which claw-free graphs are perfectly orderable?
