Triangulating 3-Colored Graphs

DOI10.1137/0405019MaRDI QIDQ4012447zbMATH OpenOpenAlexFDO

Authors Sampath Kannan, Tandy J. Warnow

Publication date 27 September 1992

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0405019

zbMATH Keywords

3-colored graphschordal graphcoloringlinear algorithmperfect phylogeny problemtriangulating colored graph problem

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Genetics and epigenetics (92D10) Problems related to evolution (92D15)

Recommendations

• A simple linear time algorithm for triangulating three-colored graphs
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• scientific article; zbMATH DE number 437536
• scientific article; zbMATH DE number 52166
• Triangulating Three-Colored Graphs in Linear Time and Linear Space

Cited in

(21)

• Method of 3-colouring of graphs
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Three colorability characterized by shrinking of locally connected subgraphs into triangles
• Completing colored graphs to meet a target property
• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Tiling tripartite graphs with 3-colorable graphs
• Unique perfect phylogeny is NP-hard
• scientific article; zbMATH DE number 437536 (Why is no real title available?)
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• scientific article; zbMATH DE number 5302772 (Why is no real title available?)
• 4-Colored Triangulation of 3-Maps
• Intervalizing \(k\)-colored graphs
• scientific article; zbMATH DE number 6939351 (Why is no real title available?)
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• scientific article; zbMATH DE number 1843872 (Why is no real title available?)
• A simple linear time algorithm for triangulating three-colored graphs
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• On intervalizing k-colored graphs for DNA physical mapping
• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• Acyclic and star colorings of cographs

This page was built for publication: Triangulating 3-Colored Graphs

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