The Complexity of Adaptably k-Colouring Edge-Coloured Hypergraphs
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Given an r-uniform hypergraph G and a colouring p : E(G) → [k] of the hyperedges with up to k-colours, an adapted k-coloring of (G, p) is a vertex map ϕ : V (G) → [k] such that for every hyperedge e, there is some vertex in e such that ϕ(v) ̸= p(e). We show that for k, r ≥ 2, the problem of deciding if an instance edge coloured graph (G, p) has an adapted k-colouring is NP-complete unless (k, r) = (2, 2). In this last case, we show that the problem is polynomial time solvable.
Abstract
Given an r-uniform hypergraph G and a colouring p : E(G) → [k] of the hyperedges with up to k-colours, an adapted k-coloring of (G, p) is a vertex map ϕ : V (G) → [k] such that for every hyperedge e, there is some vertex in e such that ϕ(v) ̸= p(e). We show that for k, r ≥ 2, the problem of deciding if an instance edge coloured graph (G, p) has an adapted k-colouring is NP-complete unless (k, r) = (2, 2). In this last case, we show that the problem is polynomial time solvable.