Completing colored graphs to meet a target property

DOI10.1016/j.dam.2017.01.021zbMath1464.05147OpenAlexW2593122855MaRDI QIDQ2030434

Elaine M. Eschen, R. Sritharan, Kathryn Cook, 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 graphstrongly chordal graphcircular-arc graphcompletion problemsandwich problem

Mathematics Subject Classification ID

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

Related Items

Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths

Cites Work

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