论文标题
小直径的两分图上的着色问题
Coloring Problems on Bipartite Graphs of Small Diameter
论文作者
论文摘要
我们研究了一些限制在界直径的两分图的着色问题。首先，我们研究了$ k $ list的着色，列表$ k $ - 颜色和$ k $ - 最多最多$ d $的两部分图形上的销售扩展问题，在大多数情况下证明了NP的完整性，并且在$ 3 $ - 颜色和$ 3 $ - $ 3 $ - $ 3 $ - 预销售扩展问题的情况下，$ 3 $ - $ -D-precoloring Extensivensial问题。 这些结果中的一些是通过证明$ C_6 $形态问题的证明，在直径最多四个的两部分图上是NP完整的。尽管后一个结果已经得到证明[Vikas，2017年]，但我们将其作为替代性简单的结果。作为副产品，我们还得到了$ 3 $ -Biclique分区的NP完整分区。 [Fleischner，Mujuni，Paulusma和Szeider，2009年]提出了证明这一结果的尝试，但他们的证明存在缺陷，我们在这里识别并讨论了这些缺陷。 最后，我们证明，$ 3 $ fall的着色问题是直径最多四个的两分图上的NP完整图，并证明直径三的NP完整性也将暗示NP完整性的直径为$ 3 $ 3 $ - 固定延伸，因此可以关闭前面提到的开放式案例。这也将回答[Kratochvíl，Tuza和Voigt，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$, 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íl, Tuza, and Voigt, 2002].
