Coloring problems on bipartite graphs of small diameter (Q831342)

Summary: We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the \(k\)-List Coloring, List \(k\)-Coloring, and \(k\)-Precoloring Extension problems on bipartite graphs with diameter at most \(d\), proving 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 through a proof that the Surjective \(C_6\)-Homomorphism problem is NP-complete on bipartite graphs with diameter at most four. Although the latter result has been already proved [\textit{N. Vikas}, LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 69, 14 p. (2017; Zbl 1441.68197)], we present ours as an alternative simpler one. As a byproduct, we also get that 3-Biclique Partition is NP-complete. An attempt to prove this result was presented in [\textit{H. Fleischner} et al., Theor. Comput. Sci. 410, No. 21--23, 2045--2053 (2009; Zbl 1168.68019)], but there was a flaw in their proof, which we identify and discuss here. Finally, we prove that the 3-Fall Coloring problem is NP-complete on bipartite graphs with diameter at most four, and prove that NP-completeness for diameter three would also imply NP-completeness of 3-Precoloring Extension on diameter three, thus closing the previously mentioned open cases. This would also answer a question posed in [\textit{J. Kratochvíl} et al., Lect. Notes Comput. Sci. 2573, 310--320 (2002; Zbl 1024.05026)].