Maximum independent sets in 3- and 4-regular Hamiltonian graphs

DOI10.1016/j.disc.2010.05.028zbMath1257.05116OpenAlexW2020320404MaRDI QIDQ709325

Vladimir I. Sarvanov, Gert Sabidussi, Herbert Fleischner

Publication date: 18 October 2010

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

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

zbMATH Keywords

planar graphsNP-completenessmaximum independent set3- or 4-regular graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Related Items (13)

Multistage vertex cover ⋮ On bipartization of cubic graphs by removal of an independent set ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Feedback vertex set on Hamiltonian graphs ⋮ Temporal interval cliques and independent sets ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon ⋮ On the maximum edge-pair embedding bipartite matching ⋮ On the maximum independent set problem in subclasses of subcubic graphs ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ Large Independent Sets in Subquartic Planar Graphs

Cites Work

• Unnamed Item
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs
• A solution to a colouring problem of P. Erdős
• 3-colorability of 4-regular hamiltonian graphs

This page was built for publication: Maximum independent sets in 3- and 4-regular Hamiltonian graphs