Squares of Intersection Graphs and Induced Matchings

DOI10.1016/j.endm.2006.06.033zbMath1202.05112OpenAlexW2011344134MaRDI QIDQ3439440

No author found.

Publication date: 29 May 2007

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

Full work available at URL: https://doi.org/10.1016/j.endm.2006.06.033

zbMATH Keywords

intersection graphindependent setsimple graphinduced matchingforbidden induced subgraphsquare of graphhypegraph

Mathematics Subject Classification ID

Hypergraphs (05C65) 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• On maximum induced matchings in bipartite graphs
• Bipartite graphs without a skew star
• New results on induced matchings
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Squares of Intersection Graphs and Induced Matchings