Path-bicolorable graphs. (Extended abstract)

DOI10.1007/978-3-642-02029-2_17MaRDI QIDQ3655151zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Van Bang Le, 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

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

Recommendations

• Path-bicolorable graphs
• \(P_4\)-colorings and \(P_4\)-bipartite graphs
• Recognizing \(k\)-path graphs
• Path graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs

Cites work

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

Cited in

(4)

• scientific article; zbMATH DE number 723840 (Why is no real title available?)
• Paths in bipartite graphs with color‐inverting involutions
• Path colorings in bipartite graphs
• Path-bicolorable graphs

This page was built for publication: Path-bicolorable graphs. (Extended abstract)

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