Coloring problems on bipartite graphs of small diameter

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

list coloring precoloring extension problems

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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 [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].

Review text

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)].

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Coloring problems on bipartite graphs of small diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831342)