Skip to Main content Skip to Navigation
Journal articles

Coloring Problems on Bipartite Graphs of Small Diameter

Abstract : 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].
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03374527
Contributor : Ignasi Sau Connect in order to contact the contributor
Submitted on : Tuesday, October 12, 2021 - 10:54:10 AM
Last modification on : Friday, October 22, 2021 - 3:07:30 PM

File

Coloring-EJC.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NoDerivatives 4.0 International License

Identifiers

Collections

Citation

Victor Campos, Guilherme C.M. Gomes, Allen Ibiapina, Raul Lopes, Ignasi Sau Valls, et al.. Coloring Problems on Bipartite Graphs of Small Diameter. The Electronic Journal of Combinatorics, Open Journal Systems, 2021, 28 (2), ⟨10.37236/9931⟩. ⟨lirmm-03374527⟩

Share

Metrics

Record views

14

Files downloads

6