Geodesic
Coloring problems on bipartite graphs of small diameter
Victor A. Campos1 ; Guilherme C.M. Gomes2 ; Allen Ibiapina1 ; Raul Lopes1 ; Ignasi Sau3 ; Ana Silva
1Universidade Federal do Ceará
2Universidade Federal de Minas Gerais
3LIRMM - Université de Montpellier
The electronic journal of combinatorics, Tome 28 (2021) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the $k$-List Coloring, $k$-Coloring, and $k$-Precoloring Extension problems on bipartite graphs with diameter at most $d$, proving $\textsf{NP}$-completeness in most cases, and leaving open only the List $3$-Coloring and $3$-Precoloring Extension problems when $d=3$. Some of these results are obtained $\textsc{through}$ a proof that the Surjective $C_6$-Homomorphism problem is $\textsf{NP}$-complete on bipartite graphs with diameter at most four. Although the latter result has been already proved [Vikas, 2017], we present ours as an alternative simpler one. As a byproduct, we also get that $3$-Biclique Partition is $\textsf{NP}$-complete. An attempt to prove this result was presented in [Fleischner, Mujuni, Paulusma, and Szeider, 2009], but there was a flaw in their proof, which we identify and discuss here. Finally, we prove that the $3$-Fall Coloring problem is $\textsf{NP}$-complete on bipartite graphs with diameter at most four, and prove that $\textsf{NP}$-completeness for diameter three would also imply $\textsf{NP}$-completeness of $3$-Precoloring Extension on diameter three, thus closing the previously mentioned open cases. This would also answer a question posed in [Kratochvíl, Tuza, and Voigt, 2002].
DOI : 10.37236/9931
Classification : 05C15, 05C12, 68Q17
Mots-clés : list coloring, precoloring extension problems

Victor A. Campos  1   ; Guilherme C.M. Gomes  2   ; Allen Ibiapina  1   ; Raul Lopes  1   ; Ignasi Sau  3   ; Ana Silva 

1 Universidade Federal do Ceará
2 Universidade Federal de Minas Gerais
3 LIRMM - Université de Montpellier 
@article{10_37236_9931,
     author = {Victor A. Campos and Guilherme C.M. Gomes and Allen Ibiapina and Raul Lopes and Ignasi Sau and Ana Silva},
     title = {Coloring problems on bipartite graphs of small diameter},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {2},
     doi = {10.37236/9931},
     zbl = {1464.05143},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9931/}
}
TY  - JOUR
AU  - Victor A. Campos
AU  - Guilherme C.M. Gomes
AU  - Allen Ibiapina
AU  - Raul Lopes
AU  - Ignasi Sau
AU  - Ana Silva
TI  - Coloring problems on bipartite graphs of small diameter
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9931/
DO  - 10.37236/9931
ID  - 10_37236_9931
ER  - 
%0 Journal Article
%A Victor A. Campos
%A Guilherme C.M. Gomes
%A Allen Ibiapina
%A Raul Lopes
%A Ignasi Sau
%A Ana Silva
%T Coloring problems on bipartite graphs of small diameter
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9931/
%R 10.37236/9931
%F 10_37236_9931
Victor A. Campos; Guilherme C.M. Gomes; Allen Ibiapina; Raul Lopes; Ignasi Sau; Ana Silva. Coloring problems on bipartite graphs of small diameter. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9931

Cité par Sources :