# The Library

### Boundary properties of graphs for algorithmic graph problems

Tools

Korpelainen, Nicholas, Lozin, Vadim V., Malyshev, Dmitriy S. and Tiskin, Alexander.
(2011)
*Boundary properties of graphs for algorithmic graph problems.*
Theoretical Computer Science, Vol.412
(No.29).
pp. 3545-3554.
ISSN 0304-3975

**Full text not available from this repository.**

Official URL: http://dx.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.

Item Type: | Journal Article |
---|---|

Subjects: | Q Science > QA Mathematics |

Divisions: | Faculty of Science > Computer Science Faculty of Science > Mathematics |

Library of Congress Subject Headings (LCSH): | Computational complexity, Hamiltonian graph theory, Graph theory, Graph coloring |

Journal or Publication Title: | Theoretical Computer Science |

Publisher: | Elsevier Science BV |

ISSN: | 0304-3975 |

Official Date: | 1 July 2011 |

Volume: | Vol.412 |

Number: | No.29 |

Page Range: | pp. 3545-3554 |

Identification Number: | 10.1016/j.tcs.2011.03.001 |

Status: | Peer Reviewed |

Publication Status: | Published |

Access rights to Published version: | Restricted or Subscription Access |

Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications (DIMAP), Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFFI), Gosudarstvennyĭ universitet Vysshai︠a︡ shkola ėkonomiki (Russia) (GU VShĖ), FAP |

Grant number: | 10-01-00357-a (RFFI), 61.1 (GU VShĖ), 2010-1.3.1-111-017-012 (FAP) |

References: | [1] V.E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskret. Math. 4 (2) (1992) 148–157 (in Russian); translation in Discrete |

URI: | http://wrap.warwick.ac.uk/id/eprint/38771 |

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

### Actions (login required)

View Item |