Some completion problems for graphs without chordless cycles of prescribed lengths

DOI10.1016/J.DAM.2019.05.017MaRDI QIDQ2274074zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Mathematics Subject Classification ID

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

Recommendations

• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• scientific article; zbMATH DE number 861401
• On the interval completion of chordal graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• On the length of longest chordless cycles
• On the girth of extremal graphs without shortest cycles
• scientific article; zbMATH DE number 3950581
• scientific article; zbMATH DE number 4127262
• On the size of graphs without repeated cycle lengths
• Chordal completions of planar graphs

Cites work

• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Chordal bipartite completion of colored graphs
• Completing colored graphs to meet a target property
• Computing the Minimum Fill-In is NP-Complete
• Detecting even holes
• Even-hole-free graphs part II: Recognition algorithm
• Graph Classes: A Survey
• 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
• On the forbidden induced subgraph probe and sandwich problems
• On the forbidden induced subgraph sandwich problem
• The chain graph sandwich problem
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The hardness of intervalizing four colored caterpillars
• The Proper Interval Colored Graph problem for caterpillar trees
• 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

(6)

• Completing colored graphs to meet a target property
• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• Chordal bipartite completion of colored graphs
• On the complexity of certain completion problems
• Completing colored graphs to meet a target property
• scientific article; zbMATH DE number 5521219 (Why is no real title available?)

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

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