Path-Bicolorable Graphs

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

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

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 graphs; linear-time recognition; \(P _{3}\)-bicolorable graphs; \(P _{4}\)-bicolorable graphs

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

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