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

DOI10.15507/2079-6900.21.201902.215-221MaRDI QIDQ5884909zbMATH OpenOpenAlexWikidataFDO

Authors Dmitrii V. Sirotkin, D. S. Malyshev

Publication date 24 March 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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)