Bipartable graphs

DOI10.1016/0095-8956(88)90050-0MaRDI QIDQ1080439zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90050-0

zbMATH Keywords

bipartite graphoptimal coloringperfectly orderable graphspolynomial algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Review text

We consider a construction which associates with a graph G another graph G' such that if G' is a bipartite graph, G is perfectly orderable. For such a graph G we give a polynomial algorithm for an optimal coloring by delivering a perfect order on his nodes. This class of graphs is shown to be different from the known classes of perfectly orderable graphs.

Recommendations

• Bipartization of graphs
• Bipartite bithreshold graphs
• Graphoidal bipartite graphs
• Bipartite subgraphs
• Bisplit graphs
• scientific article; zbMATH DE number 1194938
• scientific article; zbMATH DE number 5296402
• Bipartite-perfect graphs
• Bipartite-perfect graphs
• On the bipartition of graphs

Cites work

• Four classes of perfectly orderable graphs
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• On brittle graphs
• Tolerance graphs
• Which line-graphs are perfectly orderable?

Cited in

(14)

• Nearly bipartite graphs
• Bipartite-perfect graphs
• Recognition of some perfectly orderable graph classes
• Bisimplicial edges in bipartite graphs
• Bipartite-perfect graphs
• scientific article; zbMATH DE number 5348111 (Why is no real title available?)
• scientific article; zbMATH DE number 4010572 (Why is no real title available?)
• Bipartite designs
• On bipartite‐mixed graphs
• scientific article; zbMATH DE number 6469239 (Why is no real title available?)
• scientific article; zbMATH DE number 7324127 (Why is no real title available?)
• Which claw-free graphs are perfectly orderable?
• Bipartitions of oriented graphs
• Bipolarizable graphs

This page was built for publication: Bipartable graphs

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