## Abstract

For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of P_{t}-free graphs. We show that for every odd k ≥ 5 the C_{k}-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P_{9}-free graphs. On the other hand, we prove that the extension version of C_{k}-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw.

Original language | English (US) |
---|---|

Title of host publication | 27th Annual European Symposium on Algorithms, ESA 2019 |

Editors | Michael A. Bender, Ola Svensson, Grzegorz Herman |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771245 |

DOIs | |

State | Published - Sep 2019 |

Event | 27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany Duration: Sep 9 2019 → Sep 11 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 144 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 27th Annual European Symposium on Algorithms, ESA 2019 |
---|---|

Country/Territory | Germany |

City | Munich/Garching |

Period | 9/9/19 → 9/11/19 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Computational complexity
- Forbidden induced subgraph
- Hereditary class
- Homomorphism

## Fingerprint

Dive into the research topics of 'Complexity of C_{K}-coloring in hereditary classes of graphs'. Together they form a unique fingerprint.