Path parity and perfection

DOI10.1016/S0012-365X(96)00174-4zbMath0879.05053WikidataQ126633881 ScholiaQ126633881MaRDI QIDQ1356748

Frédéric Maffray, Hazel Everett, Oscar Porto, Bruce A. Reed, Cláudia Linhares Sales, Celina M. Herrera de Figueiredo

Publication date: 12 January 1998

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

zbMATH Keywords

holesperfect grapheven paircontractile graphsodd pairstretchers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (9)

On dart-free perfectly contractile graphs ⋮ Coloring the cliques of line graphs ⋮ From matchings to independent sets ⋮ Even pairs in claw-free perfect graphs ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ Finding induced paths of given parity in claw-free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithms for maximum weight induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure of bull-free perfect graphs
• Counterexamples to three conjectures concerning perfect graphs
• Which claw-free graphs are perfectly orderable?
• Weakly triangulated graphs
• Perfectly contractile graphs
• On the complexity of recognizing perfectly orderable graphs
• Alternating orientation and alternating colouration of perfect graphs
• Perfectly orderable graphs are quasi-parity graphs: a short proof
• Bull-free Berge graphs are perfect
• A new conjecture about minimal imperfect graphs
• On a conjecture of Meyniel
• A new property of critical imperfect graphs and some consequences
• No antitwins in minimal imperfect graphs
• A fast algorithm for coloring Meyniel graphs
• Opposition graphs are strict quasi-parity graphs
• Recognizing claw-free perfect graphs
• Star-cutsets and perfect graphs
• Some properties of minimal imperfect graphs
• Even pairs in claw-free perfect graphs
• On the complexity of testing for odd holes and induced odd paths
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Algorithms on clique separable graphs
• Quasi-parity and perfect graphs
• On planar perfectly contractile graphs
• Building counterexamples
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• An efficient algorithm for finding a two-pair, and its applications
• Recognizing bull-free perfect graphs
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Normal hypergraphs and the perfect graph conjecture
• Which line-graphs are perfectly orderable?
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• The Strong Perfect Graph Conjecture for Planar Graphs
• A note on even pairs

This page was built for publication: Path parity and perfection