Which claw-free graphs are perfectly orderable?

DOI10.1016/0166-218X(93)90221-9MaRDI QIDQ686245zbMATH OpenFDO

Authors Vašek Chvátal

Publication date 13 March 1994

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

zbMATH Keywords

characterizationclawNP-completeclaw-free graphscomplements of bipartite graphsline- graphsperfect linear orderperfectly orderable

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (05C99) Ordered structures (06F99)

Recommendations

• Some classes of perfectly orderable graphs
• Four classes of perfectly orderable graphs
• Which line-graphs are perfectly orderable?
• On the complexity of recognizing perfectly orderable graphs
• New classes of perfectly orderable graphs

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• An algorithm for finding clique cut-sets
• Bipartable graphs
• Characterizations of totally balanced matrices
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Four classes of perfectly orderable graphs
• On brittle graphs
• On rigid circuit graphs
• On the complexity of recognizing perfectly orderable graphs
• Recognizing claw-free perfect graphs
• Some classes of perfectly orderable graphs
• Totally-Balanced and Greedy Matrices
• Which claw-free graphs are perfectly orderable?
• Which line-graphs are perfectly orderable?
• \(P_ 4\)-comparability graphs

Cited in

(21)

• Even pairs in claw-free perfect graphs
• The maximum clique problem
• On dart-free perfectly contractile graphs
• Path parity and perfection
• On opposition graphs, coalition graphs, and bipartite permutation graphs
• On the online track assignment problem
• Strongly perfect claw‐free graphs—A short proof
• A note on perfectly orderable graphs
• Completely separable graphs
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• Claw-free graphs---a survey
• Bipartite Analogues of Comparability and Cocomparability Graphs
• A charming class of perfectly orderable graphs
• Which line-graphs are perfectly orderable?
• Which claw-free graphs are strongly perfect?
• Characterization and recognition of some opposition and coalition graph classes
• Recognizing claw-free perfect graphs
• Which claw-free graphs are perfectly orderable?
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• All variations on perfectly orderable graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs

This page was built for publication: Which claw-free graphs are perfectly orderable?

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