Coloring Problems on Bipartite Graphs of Small Diameter - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2021

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].
Fichier principal
Vignette du fichier
Coloring-EJC.pdf (402.78 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Licence

Dates and versions

lirmm-03374527 , version 1 (12-10-2021)

Licence

Identifiers

Cite

Victor A Campos, Guilherme C.M. Gomes, Allen Ibiapina, Raul Lopes, Ignasi Sau, et al.. Coloring Problems on Bipartite Graphs of Small Diameter. The Electronic Journal of Combinatorics, 2021, 28 (2), pp.#P2.14. ⟨10.37236/9931⟩. ⟨lirmm-03374527⟩
43 View
32 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More