The structure of well-covered graphs and the complexity of their recognition problems
From MaRDI portal
Publication:1354731
DOI10.1006/jctb.1996.1742zbMath0873.05074OpenAlexW2084977359MaRDI QIDQ1354731
Publication date: 26 October 1997
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1996.1742
characterizationpolynomial time algorithmmatchingsrecognitionindependent setswell-covered graphsequimatchable graphs
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (32)
Recognizing well covered graphs of families with special \(P _{4}\)-components ⋮ Well-covered triangulations. IV ⋮ The structure of well-covered graphs with no cycles of length 4 ⋮ Graphs with maximal induced matchings of the same size ⋮ The well-covered dimension of random graphs ⋮ Extending Berge's and Favaron's results about well-covered graphs ⋮ On CIS circulants ⋮ Triangle‐free equimatchable graphs ⋮ Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7 ⋮ On the structure of 4-regular planar well-covered graphs ⋮ Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\) ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Well-covered graphs with constraints on \(\Delta\) and \(\delta\) ⋮ On well-covered triangulations. I ⋮ Graphs vertex-partitionable into strong cliques ⋮ On relating edges in graphs without cycles of length 4 ⋮ ModelingK-coteries by well-covered graphs ⋮ Weighted well-covered claw-free graphs ⋮ On two extensions of equimatchable graphs ⋮ On well-covered pentagonalizations of the plane ⋮ On well-covered triangulations. II. ⋮ On well-covered triangulations. III ⋮ Complexity results for generating subgraphs ⋮ On the well-coveredness of Cartesian products of graphs ⋮ Weighted well-covered graphs without cycles of lengths 5, 6 and 7 ⋮ Greedily constructing maximal partial \(f\)-factors ⋮ On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6 ⋮ Mind the independence gap ⋮ The Clique Corona Operation and Greedoids ⋮ Recognizing Generating Subgraphs Revisited ⋮ Well-covered graphs without cycles of lengths 4, 5 and 6 ⋮ Efficient recognition of equimatchable graphs
Cites Work
This page was built for publication: The structure of well-covered graphs and the complexity of their recognition problems
