Path-Bicolorable Graphs

DOI10.1007/978-3-642-02029-2_17zbMath1194.05036OpenAlexW1543659517MaRDI QIDQ3655151

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

Publication date: 7 January 2010

Published in: Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02029-2_17

zbMATH Keywords

bipartite graphslinear-time recognition\(P _{3}\)-bicolorable graphs\(P _{4}\)-bicolorable graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) 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