Some completion problems for graphs without chordless cycles of prescribed lengths

DOI10.1016/j.dam.2019.05.017zbMath1419.05066OpenAlexW2955728877WikidataQ127596956 ScholiaQ127596956MaRDI QIDQ2274074

Arthur H. Busch, R. Sritharan

Publication date: 19 September 2019

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

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

zbMATH Keywords

completion problem\(C_4\)-free graphssandwich problem\((C_4, \dots, C_s)\)-free graphs\((C_4, C_6, \ldots, C_{2 s})\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)

Related Items (1)

Bipartite completion of colored graphs avoiding chordless cycles of given lengths

Cites Work

• On the forbidden induced subgraph sandwich problem
• The chain graph sandwich problem
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• On the forbidden induced subgraph probe and sandwich problems
• Completing colored graphs to meet a target property
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Chordal bipartite completion of colored graphs
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Even-hole-free graphs part II: Recognition algorithm
• The Proper Interval Colored Graph problem for caterpillar trees
• Computing the Minimum Fill-In is NP-Complete
• Triangulating 3-Colored Graphs
• Graph Classes: A Survey
• Triangulating Vertex-Colored Graphs
• Detecting even holes
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• Graph Sandwich Problems
• Two strikes against perfect phylogeny
• The hardness of intervalizing four colored caterpillars
• On intervalizing \(k\)-colored graphs for DNA physical mapping

This page was built for publication: Some completion problems for graphs without chordless cycles of prescribed lengths