Triangulating 3-Colored Graphs

DOI10.1137/0405019zbMath0779.05020OpenAlexW2159596482MaRDI QIDQ4012447

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

chordal graphcoloringlinear algorithmperfect phylogeny problem3-colored graphstriangulating colored graph problem

Mathematics Subject Classification ID

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

Related Items (10)

Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ Acyclic and star colorings of cographs ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ Intervalizing k-colored graphs ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Completing colored graphs to meet a target property ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Unnamed Item

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