The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
share
A proper coloring of a graph is 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 graph is odd if for every non-isolated vertex v, there is a color appearing an odd number of times in the neighborhood of v. For an integer k, the PCF k-Coloring problem asks whether an input graph admits a proper conflict-free k-coloring and the Odd k-Coloring asks whether an input graph admits an odd k-coloring. We show that for every integer k≥3, both problems are NP-complete, even if the input graph is bipartite. Furthermore, we show that the PCF 4-Coloring problem is NP-complete when the input graph is planar.
READ FULL TEXT