Even and odd pairs in comparability and in \(P_4\)-comparability graphs

DOI10.1016/S0166-218X(98)00139-5zbMath0927.68066MaRDI QIDQ1283809

John G. Gimbel, Célia Picinin de Mello, Celina M. Herrera de Figueiredo, Jayme Luiz Szwarcfiter

Publication date: 31 May 1999

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

zbMATH Keywords

\(P_4\)-comparability graphsparity path problems

Mathematics Subject Classification ID

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

Related Items (1)

Finding induced paths of given parity in claw-free graphs

Cites Work

• Unnamed Item
• A linear algorithm for the group path problem on chordal graphs
• Efficient reduction for path problems on circular-arc graphs
• A new property of critical imperfect graphs and some consequences
• \(P_ 4\)-comparability graphs
• On the complexity of testing for odd holes and induced odd paths
• 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
• Some classes of perfectly orderable graphs

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