Adaptive multicolouring (Q1586355)

A weighted graph \(G_c\) is a pair \((G, c)\) where \(G\) is a graph with vertex set \(V\) and \(c\) is a positive integer weight vector \((c_1,\dots,c_v)\). A multicolouring of \(G_c\) is an assigment of \(c_i\) colours to each vertex \(v_i\in V\), such that no two adjacent have any colour in common. The chromatic number of a weighted graph \(G_c\) is the minimal number of colours needed for multicolouring \(G_c\). The authors consider the problem of adaptive multicolouring, that is the problem of finding a multicolouring for a graph and each of a sequence of changing weight vectors. The number of colours needed for an adaptive multicolouring for the class of \(k\)-colourable graphs is established.