{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:16Z","timestamp":1753893856134,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the $k$-List Coloring, $k$-Coloring, and $k$-Precoloring Extension problems on bipartite graphs with diameter at most $d$, proving $\\textsf{NP}$-completeness in most cases, and leaving open only the List $3$-Coloring and $3$-Precoloring Extension problems when $d=3$.\r\nSome of these results are obtained $\\textsc{through}$ a proof that the Surjective $C_6$-Homomorphism problem is $\\textsf{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 $\\textsf{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.\r\nFinally, we prove that the $3$-Fall Coloring problem is $\\textsf{NP}$-complete on bipartite graphs with diameter at most four, and prove that $\\textsf{NP}$-completeness for diameter three would also imply $\\textsf{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\u00edl, Tuza, and Voigt, 2002].<\/jats:p>","DOI":"10.37236\/9931","type":"journal-article","created":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T02:34:30Z","timestamp":1619145270000},"source":"Crossref","is-referenced-by-count":1,"title":["Coloring Problems on Bipartite Graphs of Small Diameter"],"prefix":"10.37236","volume":"28","author":[{"given":"Victor A.","family":"Campos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guilherme C.M.","family":"Gomes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allen","family":"Ibiapina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raul","family":"Lopes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2021,4,23]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p14\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p14\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T02:34:31Z","timestamp":1619145271000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v28i2p14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,23]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,4,9]]}},"URL":"https:\/\/doi.org\/10.37236\/9931","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2021,4,23]]},"article-number":"P2.14"}}