Coloring Problems on Bipartite Graphs of Small Diameter
share
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≥ 4 and every d≥ 3, and for k=3 and d≥ 4, and that List k-Coloring is polynomial when d=2 (i.e., on complete bipartite graphs) for every k ≥ 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ára, 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íl, Tuza, and Voigt [Proc. of WG 2002].
READ FULL TEXT