The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs

Jungho Ahn, Seonghyuk Im, Sang-il Oum

A proper coloring of a graph is \emph{proper conflict-free} if every non-isolated vertex $v$ has a neighbor whose color is unique in the neighborhood of $v$. A proper coloring of a…