A note on graphs contraction-critical with respect to independence number

DOI10.1016/j.disc.2014.02.004zbMath1288.05196MaRDI QIDQ2449144

Michael D. Plummer, Akira Saito

Publication date: 6 May 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2014.02.004

zbMATH Keywords

matching; independent set; polynomial algorithm; contraction-critical; 1-extendable

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Cites Work

• Contractions, cycle double covers, and cyclic colorings in locally connected graphs
• Graphs with unique maximum independent sets
• Matching theory
• Non-Hamiltonian bicubic graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On defect-d matchings in graphs
• Hamilton cycles in 2-connected regular bipartite graphs
• A survey on contractible edges in graphs of a prescribed vertex connectivity
• WELL-COVERED GRAPHS: A SURVEY
• Reducibility among Combinatorial Problems
• On the Core of a Graph^†
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item