2022 Combinatorics Workshop

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

1 Oct 2022, 15:40

20m

Contributed talk Session 4

Speaker

Mr Jungho Ahn (KAIST & IBS DIMAG)

Description

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\ge 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.