Even and odd pairs in comparability and in P₄-comparability graphs

DOI10.1016/S0166-218X(98)00139-5zbMATH Open0927.68066MaRDI QIDQ1283809FDOQ1283809

Authors: Celina M. H. de Figueiredo, John Gimbel, Célia P. de Mello, Jayme L. Szwarcfiter 

Publication date: 31 May 1999

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

Recommendations

• scientific article; zbMATH DE number 2081001
• scientific article; zbMATH DE number 1953107
• Even pairs in planar Berge graphs
• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation

zbMATH Keywords

\(P_4\)-comparability graphsparity path problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Some classes of perfectly orderable graphs
• Title not available (Why is that?)
• A new property of critical imperfect graphs and some consequences
• On the complexity of testing for odd holes and induced odd paths
• \(P_ 4\)-comparability graphs
• A linear algorithm for the group path problem on chordal graphs
• Efficient reduction for path problems on circular-arc graphs
• Sources and sinks in comparability graphs
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• The parity path problem on some subclasses of perfect graphs

Cited In (1)

• Finding induced paths of given parity in claw-free graphs

This page was built for publication: Even and odd pairs in comparability and in \(P_4\)-comparability graphs

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