Completing colored graphs to meet a target property
From MaRDI portal
Publication:2030434
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
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
