Polynomial-time approximation algorithms for the coloring problem in some cases |
| |
Authors: | D S Malyshev |
| |
Institution: | 1.National Research University Higher School of Economics,Nizhny Novgorod,Russia |
| |
Abstract: | We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|