The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916896731824128 |
|---|---|
| author | Ahn, Jungho Im, Seonghyuk Oum, Sang-il |
| author_facet | Ahn, Jungho Im, Seonghyuk Oum, Sang-il |
| contents | 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 graph is \emph{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 \textsc{PCF $k$-Coloring} problem asks whether an input graph admits a proper conflict-free $k$-coloring and the \textsc{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 \textsc{PCF $4$-Coloring} problem is NP-complete when the input graph is planar. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_08330 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs Ahn, Jungho Im, Seonghyuk Oum, Sang-il Computational Complexity Combinatorics 05C15, 68Q17 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 graph is \emph{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 \textsc{PCF $k$-Coloring} problem asks whether an input graph admits a proper conflict-free $k$-coloring and the \textsc{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 \textsc{PCF $4$-Coloring} problem is NP-complete when the input graph is planar. |
| title | The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs |
| topic | Computational Complexity Combinatorics 05C15, 68Q17 |
| url | https://arxiv.org/abs/2208.08330 |