Recognizing relating edges in graphs without cycles of length 6

DOI10.1007/S00373-025-02930-9MaRDI QIDQ6964823zbMATH OpenFDO

Authors Vadim E. Levit, David Tankus

Publication date 4 July 2025

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00373-025-02930-9

zbMATH Keywords

independent setrelating edgeSAT problemshedding vertexW2-graphwell-covered graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• 1-well-covered graphs revisited
• W₂-graphs and shedding vertices
• A characterization of well covered graphs of girth 5 or greater
• Beyond recognizing well-covered graphs
• Complexity results for generating subgraphs
• Complexity results for well‐covered graphs
• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• Local Structure When All Maximal Independent Sets Have Equal Weight
• On relating edges in graphs without cycles of length 4
• On some subclasses of well-covered graphs
• Recognizing \(\text{W}_2\) graphs
• Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
• The structure of well-covered graphs with no cycles of length 4
• Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
• Vertex decomposable graphs and obstructions to shellability
• Well-covered graphs without cycles of lengths 4, 5 and 6

This page was built for publication: Recognizing relating edges in graphs without cycles of length 6

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