Path-bicolorable graphs

DOI10.1007/s00373-010-1007-9zbMath1234.05077OpenAlexW1978057479MaRDI QIDQ659746

Martin Charles Golumbic, Van Bang Le, Andreas Brandstädt, Marina Lipshteyn

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-010-1007-9

zbMATH Keywords

bipartite graphs\(P_3\)-bicolorable graphs\(P_4\)-bicolorable graphs3-leaf powerslinear time recognition

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Cites Work

• More about subcolorings
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
• Structure and linear time recognition of 3-leaf powers
• The strong perfect graph theorem
• Split graphs of Dilworth number 2
• A note on superbrittle graphs
• Alternating orientation and alternating colouration of perfect graphs
• Complement reducible graphs
• Modular decomposition and transitive orientation
• The subchromatic number of a graph
• Chordal probe graphs
• On Graph Powers for Leaf-Labeled Trees
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Graph Classes: A Survey
• Graph Subcolorings: Complexity and Algorithms
• Split-Perfect Graphs: Characterizations and Algorithmic Use
• P-Components and the Homogeneous Decomposition of Graphs

This page was built for publication: Path-bicolorable graphs