Boundary properties of graphs for algorithmic graph problems

Korpelainen, Nicholas; Lozin, Vadim V.; Malyshev, Dmitriy S. and Tiskin, Alexander (2011). Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, 412(29) pp. 3545–3554.

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

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI