Even and odd pairs in linegraphs of bipartite graphs

DOI10.1016/0195-6698(95)90085-3zbMath0815.05052OpenAlexW2049607397MaRDI QIDQ1345522

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

zbMATH Keywords

bipartite graphsline graphsinduced paths

Mathematics Subject Classification ID

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

Related Items

Even pairs in claw-free perfect graphs ⋮ Coloring square-free Berge graphs ⋮ Even pairs and prism corners in square-free Berge graphs

Cites Work

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