Bipartite completion of colored graphs avoiding chordless cycles of given lengths

DOI10.1016/J.DAM.2022.03.027MaRDI QIDQ2146743zbMATH OpenOpenAlexFDO

Authors Elaine M. Eschen, R. Sritharan

Publication date 21 June 2022

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

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

zbMATH Keywords

bipartite completionchordal bipartite graphsgraph sandwich problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Chordal bipartite completion of colored graphs
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Completing colored graphs to meet a target property
• Completing colored graphs to meet a target property
• On the forbidden induced subgraph sandwich problem

Cites work

• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Characterizations of totally balanced matrices
• Chordal bipartite completion of colored graphs
• Completing colored graphs to meet a target property
• Computing the Minimum Fill-In is NP-Complete
• Doubly Lexical Orderings of Matrices
• Efficiency of a Good But Not Linear Set Union Algorithm
• Graph Sandwich Problems
• On intervalizing k-colored graphs for DNA physical mapping
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Some completion problems for graphs without chordless cycles of prescribed lengths
• The hardness of intervalizing four colored caterpillars
• The Proper Interval Colored Graph problem for caterpillar trees
• Totally-Balanced and Greedy Matrices
• 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)

• 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
• Completing colored graphs to meet a target property

This page was built for publication: Bipartite completion of colored graphs avoiding chordless cycles of given lengths

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