Maximum induced matching of hexagonal graphs

DOI10.1007/s40840-015-0288-9zbMath1339.05307OpenAlexW2222374963MaRDI QIDQ726519

Rija Erveš, Petra Šparl

Publication date: 11 July 2016

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40840-015-0288-9

zbMATH Keywords

matchinghexagonal graphmaximum induced matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

3-path vertex cover and dissociation number of hexagonal graphs ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the induced matching problem
• Simpler multicoloring of triangle-free hexagonal graphs
• Irredundancy in circular arc graphs
• Maximum induced matching problem on hhd-free graphs
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• On the \(k\)-path vertex cover of some graph products
• On the approximability of the maximum induced matching problem
• 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs
• New results on induced matchings
• Minimum \(k\)-path vertex cover
• Multicoloring of cannonball graphs
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• The strong chromatic index ofC4-free graphs
• Paths, Trees, and Flowers
• Approximation and Online Algorithms