Copy the page URI to the clipboard
Korpelainen, Nicholas; Lozin, Vadim V.; Malyshev, Dmitriy S. and Tiskin, Alexander
(2011).
DOI: https://doi.org/10.1016/j.tcs.2011.03.001
Abstract
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and vertex k-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any k > 3 there is a continuum of boundary classes for vertex k-colorability.
Viewing alternatives
Metrics
Public Attention
Altmetrics from AltmetricNumber of Citations
Citations from DimensionsItem Actions
Export
About
- Item ORO ID
- 38889
- Item Type
- Journal Item
- ISSN
- 0304-3975
- Keywords
- computational complexity; hereditary class; Hamiltonian cycle; vertex colorability
- Academic Unit or School
-
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM) - Copyright Holders
- © 2011 Elsevier B.V.
- Depositing User
- Nicholas Korpelainen