Role colouring graphs in hereditary classes
| Autor: | Christopher Purcell, M. Puck Rombach |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Vertex (graph theory)
Class (set theory) Loop (graph theory) General Computer Science Complete graph 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Combinatorics Boundary class 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Prime power Time complexity Mathematics |
| Zdroj: | Theoretical Computer Science. 876:12-24 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2021.05.010 |
| Popis: | A locally surjective homomorphism from a graph G to a graph H is called an H-role colouring of G. Deciding the existence of such a colouring with | H | = k is known to be NP-hard even under substantial restrictions on the input graph G. We study the family of hereditary classes for which the problem can be solved efficiently. Our main result is the first boundary class for this problem; that is, a minimal obstruction to solving the problem efficiently in a finitely defined hereditary class. We also give the first boundary class for the related k-coupon colouring problem, in which H is a complete graph with each vertex incident to a loop, when k is a prime power. As additional results, we show that 2-role colouring 2 K 2 -free graphs and 2-coupon colouring cographs can be done in linear time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect