Max-coloring of vertex-weighted graphs (Q5964985)

A proper vertex coloring of a graph \(G\) is a partition \(\{A_1, \dots, A_k\}\) of the vertex set \(V(G)\) into stable sets. For a graph \(G\) with a positive vertex weight \(c: V(G) \to (0, \infty)\), denoted by \((G, c)\), let \(\chi (G, c)\) be the minimum value of \(\sum_{i = 1}^k \max_{v \in A_i}c(v)\) over all proper vertex colorings \(\{A_1, \dots, A_k\}\) of \(G\) and \(\natural\chi(G, c)\) the minimum value of \(k\) for a proper vertex coloring \(\{A_1, \dots, A_k\}\) of \(G\) such that \(\sum_{i = 1}^k \max_{v \in A_i}c(v) = \chi(G, c)\). In this paper, the author establishes an upper bound on \(\natural\chi(G, c)\) for a weighted \(r\)-colorable graph \((G, c)\). A Nordhaus-Gaddum type inequality for \(\chi(G, c)\) is also proved. The following results are proved in the context of perfect graphs. Theorem. A graph \(G\) is \(c\)-perfect for all vertex weights \(c\) if and only if it is a complete \(r\)-partite graph for some \(r\). Theorem. If \(G\) is \(P_4\)-free (or equivalently a cograph), then \(G\) is \(c\)-perfect for any vertex-weight \(c\) satisfying \((C1)\) for any three vertices \(x, y, z\) among which there is exactly one edge \(yz\), we have \(c(x) \leq \max\{c(y), c(z)\}\).