Photo from wikipedia
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… Click to show full 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:
coloring problem;
time approximation;
polynomial time;
problem
Journal Title: Journal of Combinatorial Optimization
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Journal of Combinatorial Optimization
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!