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

DOI10.1016/S0166-218X(98)00139-5MaRDI QIDQ1283809zbMATH OpenFDO

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)

Full work available at URL https://doi.org/10.1016/S0166-218X(98)00139-5

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)

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

Cites work

• \(P_ 4\)-comparability graphs
• A linear algorithm for the group path problem on chordal graphs
• A new property of critical imperfect graphs and some consequences
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Efficient reduction for path problems on circular-arc graphs
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• On the complexity of testing for odd holes and induced odd paths
• Some classes of perfectly orderable graphs
• Sources and sinks in comparability 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)