We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. We prove that the k-List Coloring, List k-Coloring, and k-Precoloring Extension problems are NP-complete on bipartite graphs with diameter at most d, for every k%DIFDELCMD < \ge %%% 4 and every d%DIFDELCMD < \ge %%% 3, and for k=3 and d%DIFDELCMD < \ge %%% 4, and that List k-Coloring is polynomial when d=2 (i.e., on complete bipartite graphs) for every k \geq 3. Since k-List Coloring was already known to be NP-complete on complete bipartite graphs, and polynomial for k=2 on general graphs, the only remaining open problems are List 3-Coloring and 3-Precoloring Extension  when d=3. We also prove that the Surjective C_6-Homomorphism problem is NP-complete on bipartite graphs with diameter at most 4, answering a question posed by Bodirsky, K\'ara, and Martin [ Discret. Appl. Math. 2012 .  As a byproduct, we get that deciding whether V(G) can be partitioned into 3 subsets each inducing a complete bipartite graph is NP-complete. An attempt to prove this result was presented by Fleischner, Mujuni, Paulusma, and Szeider Theor. Comput. Sci. 2009], but we realized that there was an apparently non-fixable flaw in their proof  . Finally, we prove that the 3-Fall Coloring problem is NP-complete on bipartite graphs with diameter at most 4, and give a polynomial reduction from 3-Fall Coloring on bipartite graphs with diameter 3 to 3-Precoloring Extension on bipartite graphs with diameter 3. The latter result implies that if 3-Fall Coloring is NP-complete on these graphs, then the complexity gaps mentioned above for List k-Coloring and k-Precoloring Extension would be closed . This would also answer a question posed by Kratochv\'il, Tuza, and Voigt Proc. of WG 2002].
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, %DIFDELCMD < \ge %%% %DIFDELCMD < \ge %%% %DIFDELCMD < \ge %%% 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 [ Vikas, 2017 , 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 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 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 Kratochv\'il, Tuza, and Voigt , 2002].
R
We prove that
First, we investigate
D
are NP-complete
D
for every k
D
4 and every d
D
3, and for k=3 and d
R
4, and that List k-Coloring is polynomial when d=2 (i.e., on complete bipartite graphs) for every k \geq 3. Since k-List Coloring was already known to be NP-complete on complete bipartite graphs, and polynomial for k=2 on general graphs, the only remaining open problems are
proving NP-completeness in most cases, and leaving open only the
A
problems
R
We also prove
Some of these results are obtained through a proof
R
4, answering a question posed by Bodirsky, K\'ara, and Martin
four. Although the latter result has been already proved
D
Discret. Appl. Math. 2012
R
.
Vikas, 2017
A
, we present ours as an alternative simpler one.
R
get that deciding whether V(G) can be partitioned into 3 subsets each inducing a complete bipartite graph
also get that 3-Biclique Partition
R
by
in
R
Theor. Comput. Sci.
,
R
we realized that there was an apparently non-fixable
there was a
A
, which we identify and discuss here
R
4, and give a polynomial reduction from 3-Fall Coloring on bipartite graphs with diameter 3 to
four, and prove that NP-completeness for diameter three would also imply NP-completeness of
R
bipartite graphs with diameter 3. The latter result implies that if 3-Fall Coloring is NP-complete on these graphs, then the complexity gaps mentioned above for List k-Coloring and k-Precoloring Extension would be closed
diameter three, thus closing the previously mentioned open cases
R
by
in
R
Proc. of WG
,