On relating edges in graphs without cycles of length 4

DOI10.1016/J.JDA.2013.09.007MaRDI QIDQ2447533zbMATH OpenOpenAlexFDO

Authors Vadim E. Levit, David Tankus

Publication date 28 April 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.09.007

zbMATH Keywords

Ford and Fulkerson algorithmrelating edgeSAT problemwell-covered graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On related edges in well-covered graphs without cycles of length 4 and 6
• Well-covered graphs without cycles of lengths 4, 5 and 6
• The structure of well-covered graphs with no cycles of length 4
• Computing independent sets in graphs with large girth
• Analysis of the influence of the number of edges on the complexity of the independent set problem

Cites work

• A characterization of well covered graphs of girth 5 or greater
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Complexity results for well‐covered graphs
• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Local Structure When All Maximal Independent Sets Have Equal Weight
• Recognizing Greedy Structures
• The structure of well-covered graphs and the complexity of their recognition problems
• The structure of well-covered graphs with no cycles of length 4
• Well covered simplicial, chordal, and circular arc graphs
• Well-covered claw-free graphs

Cited in

(14)

• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Weighted well-covered graphs without cycles of lengths 5, 6 and 7
• Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
• Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
• Well-covered graphs without cycles of lengths 4, 5 and 6
• On graphs and algebraic graphs that do not contain cycles of length 4
• Weighted well-covered claw-free graphs
• Recognizing generating subgraphs revisited
• On 4-connected graphs without even cycle decompositions
• Well-covered graphs with constraints on \(\Delta\) and \(\delta\)
• Recognizing \(\text{W}_2\) graphs
• Recognizing relating edges in graphs without cycles of length 6
• Generating subgraphs in chordal graphs
• Complexity results for generating subgraphs

This page was built for publication: On relating edges in graphs without cycles of length 4

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