A constructive existence theorem related to local transformations of graphs for the independent set problem

DOI10.15507/2079-6900.21.201902.215-221OpenAlexW2955903066WikidataQ127573108 ScholiaQ127573108MaRDI QIDQ5884909FDOQ5884909

Authors: Dmitrii V. Sirotkin, D. S. Malyshev 

Publication date: 24 March 2023

Published in: Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva (Search for Journal in Brave)

Full work available at URL: https://www.mathnet.ru/eng/svmo737

Recommendations

• Local transformations of graphs preserving independence number
• The existence and uniqueness theorems associated with local transformations of graphs for the \(k\)-colorability problem
• A method of graph reduction and its applications
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem

zbMATH Keywords

independent set problemlocal transformationgraph with given properties

Mathematics Subject Classification ID

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

This page was built for publication: A constructive existence theorem related to local transformations of graphs for the independent set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5884909)