On some conjectures concerning critical independent sets of a graph

zbMath1339.05296arXiv1509.05057MaRDI QIDQ2629485

Taylor Short

Publication date: 6 July 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.05057

zbMATH Keywords

maximum matchingmaximum independent setKönig-Egerváry graphmaximum critical independent set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Critical independent sets of König-Egerváry graphs ⋮ CRITICAL DUAL SET-SYSTEMS ⋮ Some more updates on an annihilation number conjecture: pros and cons ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical and maximum independent sets of a graph ⋮ Problems on matchings and independent sets of a graph ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ DUALITY AND HEREDITARY KÖNIG-EGERVÁRY SET-SYSTEMS ⋮ Monotonic properties of collections of maximum independent sets of a graph ⋮ On an annihilation number conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• A set and collection lemma
• A characterization of the graphs in which the transversal number equals the matching number
• The critical independence number and an independence decomposition
• Graphs with equal independence and annihilation numbers
• Ear-decompositions of matching-covered graphs
• Testing for Equality between Maximum Matching and Minimum Node Covering
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Combinatorial properties of the family of maximum stable sets of a graph
• Critical and maximum independent sets of a graph
• On the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• An efficiently solvable graph partition problem to which many problems are reducible
• On maximum matchings in König-Egerváry graphs
• Using critical sets to solve the maximum independent set problem
• Vertices Belonging to All Critical Sets of a Graph
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

This page was built for publication: On some conjectures concerning critical independent sets of a graph