Even and odd pairs in linegraphs of bipartite graphs

DOI10.1016/0195-6698(95)90085-3zbMATH Open0815.05052OpenAlexW2049607397MaRDI QIDQ1345522FDOQ1345522

Authors: Stefan Hougardy 

Publication date: 8 March 1995

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0195-6698(95)90085-3

Recommendations

• Even pairs
• Bipartite graphs with even spanning trees
• Even pairs and the strong perfect graph conjecture
• Even pairs in claw-free perfect graphs
• Even pairs in planar Berge graphs

zbMATH Keywords

bipartite graphsline graphsinduced paths

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Cites Work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• Coloring perfect \((K_ 4\)-e)-free graphs
• Star-cutsets and perfect graphs
• Slim graphs
• Title not available (Why is that?)
• A new property of critical imperfect graphs and some consequences
• Alternating orientation and alternating colouration of perfect graphs
• The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Even pairs and the strong perfect graph conjecture
• A new conjecture about minimal imperfect graphs

Cited In (7)

• Coloring square-free Berge graphs
• Even pairs in claw-free perfect graphs
• Even pairs in planar Berge graphs
• Even pairs and prism corners in square-free Berge graphs
• Even graphs
• Bipartite graphs with even spanning trees
• Title not available (Why is that?)

This page was built for publication: Even and odd pairs in linegraphs of bipartite graphs

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