On relating edges in graphs without cycles of length 4

DOI10.1016/j.jda.2013.09.007zbMath1298.05255OpenAlexW2147078876MaRDI QIDQ2447533

David Tankus, Vadim E. Levit

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

SAT problemwell-covered graphrelating edgeFord and Fulkerson algorithm

Mathematics Subject Classification ID

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

Related Items (7)

Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7 ⋮ Well-covered graphs with constraints on \(\Delta\) and \(\delta\) ⋮ Weighted well-covered claw-free graphs ⋮ Complexity results for generating subgraphs ⋮ Weighted well-covered graphs without cycles of lengths 5, 6 and 7 ⋮ Recognizing Generating Subgraphs Revisited ⋮ Well-covered graphs without cycles of lengths 4, 5 and 6

Cites Work

• Unnamed Item
• Unnamed Item
• A characterization of well covered graphs of girth 5 or greater
• The structure of well-covered graphs and the complexity of their recognition problems
• Well-covered claw-free graphs
• The structure of well-covered graphs with no cycles of length 4
• Complexity results for well‐covered graphs
• Local Structure When All Maximal Independent Sets Have Equal Weight
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Recognizing Greedy Structures
• Well covered simplicial, chordal, and circular arc graphs

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