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\geq3$, 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.
Primary authors
Mr
Jungho Ahn
(KAIST & IBS DIMAG)
Prof.
Sang-il Oum
(IBS DIMAG & KAIST)
Mr
Seonghyuk Im
(KAIST & IBS ECOPRO)
