Sum coloring of bipartite graphs with bounded degree (Q1884769)

A coloring of a graph \(G=(V, E)\) is a function \(c: V \rightarrow \mathbb N\) such that, for all adjacent vertices \( v\) and \(w\), \(c(v)\not= c(w)\). Given a graph \(G=(V, E)\) and a positive integer \(k\), the chromatic sum problem (CSP) asks whether or not \(\min\sum_{v\in V} c(v)\leq k\), where the minimum is taken over all colorings \(c\) of \(G\). The sum coloring problem (SCP) asks for a (best) coloring \(c\) with minimum sum \(\sum_{v\in V} c(v)\). The authors prove that CSP is NP-complete on planar bipartite graphs with maximum degree \(\leq 5\), and can be soved in \(O(| V| ^2)\) time on bipartite graphs of maximum degree \(\leq 3\). The authors conjecture that CSP is polynomial solvable on bipartite graphs with maximum degree \(\leq 4\). They also give a \(27/26\)-approximation algorithm for SCP on bipartite graphs, improving a result proved by \textit{A. Bar-Noy} and \textit{G. Kortsarz} [J. Algorithms 28, 339-365 (1998; Zbl 0936.68076)].