WELL-COVERED GRAPHS: A SURVEY

DOI10.1080/16073606.1993.9631737zbMATH Open0817.05068OpenAlexW2014871086WikidataQ56210383 ScholiaQ56210383MaRDI QIDQ4288045FDOQ4288045

Michael D. Plummer

Publication date: 21 April 1994

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/16073606.1993.9631737

zbMATH Keywords

greedy algorithmmaximal independent setindependence numberwell- covered graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ear-decompositions of matching-covered graphs
• A characterization of well covered graphs of girth 5 or greater
• On some subclasses of well-covered graphs
• Some covering concepts in graphs
• The Factorization of Linear Graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• On maximal independent sets of vertices in claw-free graphs
• Recognizing Greedy Structures
• Very well covered graphs
• Cyclic coloration of 3-polytopes
• Complexity results for well‐covered graphs
• A characterization of the graphs in which the transversal number equals the matching number
• A Theorem on k-Saturated Graphs
• Well-covered graphs and extendability
• On 4-connected claw-free well-covered graphs
• Matching-perfect and cover-perfect graphs
• Regularisable Graphs
• Matchings in polytopal graphs

Cited In (74)

• Extending Berge's and Favaron's results about well-covered graphs
• A characterization of triangle-free Gorenstein graphs and Cohen-Macaulayness of second powers of edge ideals
• Cohen–Macaulay graphs with large girth
• The structure of well-covered graphs with no cycles of length 4
• Well-covered circulant graphs
• Cohen–Macaulay Circulant Graphs
• Independent transversals of hypergraph edges and bipartite bigraphs
• Well-covered graphs without cycles of lengths 4, 5 and 6
• A glimpse to most of the old and new results on very well-covered graphs from the viewpoint of commutative algebra
• The \(v\)-number of edge ideals
• Title not available (Why is that?)
• Recognizing well covered graphs of families with special \(P _{4}\)-components
• Detecting strong cliques
• Building graphs whose independence polynomials have only real roots
• Well-covered graphs and factors
• Strong cliques in vertex‐transitive graphs
• Well-located graphs: A collection of well-covered ones
• Complexity results for well‐covered graphs
• A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
• The well-covered dimension of random graphs
• Refinement of the equilibrium of public goods games over networks: efficiency and effort of specialized equilibria
• Roots of independence polynomials of well covered graphs
• Totally equimatchable graphs
• Cohen-Macaulay, shellable and unmixed clutters with a perfect matching of König type
• The Clique Corona Operation and Greedoids
• The size of Betti tables of edge ideals of clique corona graphs
• Recursively decomposable well-covered graphs
• Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\)
• On Gorenstein graphs
• On the structure of 4-regular planar well-covered graphs
• Well-covered triangulations. IV
• On the Cartesian product of non well-covered graphs
• Independence Complexes of Well-Covered Circulant Graphs
• Title not available (Why is that?)
• Vertex-transitive CIS graphs
• Well-hued graphs
• Modeling \(k\)-coteries by well-covered graphs
• On well-covered triangulations. II.
• On well-covered triangulations. III
• On CIS circulants
• Weighted well-covered claw-free graphs
• Mind the independence gap
• On 4-connected claw-free well-covered graphs
• Graphs vertex-partitionable into strong cliques
• The uniformity space of hypergraphs and its applications
• The structure of well-covered graphs and the complexity of their recognition problems
• On weakly connected domination in graphs. II.
• Triangulations and equality in the domination chain
• On well-covered triangulations. I
• Title not available (Why is that?)
• Greedily constructing maximal partial \(f\)-factors
• Well-totally-dominated graphs
• New results relating independence and matchings
• A revision and extension of results on 4-regular, 4-connected, claw-free graphs
• A characterization of well-covered graphs in terms of forbidden costable subgraphs
• On well-covered Cartesian products
• Well-indumatched Trees and Graphs of Bounded Girth
• Edge-stable equimatchable graphs
• Well irredundant graphs
• On well-covered pentagonalizations of the plane
• On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• A note on graphs contraction-critical with respect to independence number
• Distinct sizes of maximal independent sets on graphs with restricted girth
• Neighborhood unions and regularity in graphs
• Computing well-covered vector spaces of graphs using modular decomposition
• Recognizing well-dominated graphs is coNP-complete
• A general formula for the index of depth stability of edge ideals
• Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
• Well-forced graphs
• Buchsbaumness of the second powers of edge ideals
• On \(\alpha\)-excellent graphs
• Well-covered unitary Cayley graphs of matrix rings over finite fields and applications
• Title not available (Why is that?)

This page was built for publication: WELL-COVERED GRAPHS: A SURVEY

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