Completing colored graphs to meet a target property

DOI10.1016/J.DAM.2017.01.021MaRDI QIDQ2030434zbMATH OpenOpenAlexFDO

Authors Kathryn Cook, Elaine M. Eschen, R. Sritharan, Xiaoqiang Wang

Publication date 7 June 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.01.021

zbMATH Keywords

chordal graphcircular-arc graphstrongly chordal graphcompletion problemsandwich problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Completing colored graphs to meet a target property
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Chordal bipartite completion of colored graphs
• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• scientific article; zbMATH DE number 4051024

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 403948 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Algorithms finding tree-decompositions of graphs
• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Chordal bipartite completion of colored graphs
• Graph Sandwich Problems
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Matrix characterizations of circular-arc graphs
• Normal Helly circular-arc graphs and its subclasses
• On intervalizing \(k\)-colored graphs for DNA physical mapping
• On rigid circuit graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• On the proper intervalization of colored caterpillar trees
• Polynomial time recognition of unit circular-arc graphs
• Proper Helly Circular-Arc Graphs
• Structure theorems for some circular-arc graphs
• The clique operator on circular-arc graphs
• The hardness of intervalizing four colored caterpillars
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Triangulating 3-Colored Graphs
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• Triangulating Vertex-Colored Graphs
• Two strikes against perfect phylogeny

Cited in

(4)

• Chordal bipartite completion of colored graphs
• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Completing colored graphs to meet a target property

This page was built for publication: Completing colored graphs to meet a target property

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