Victor A Campos

Guilherme C M Gomes
email: gcm.gomes@dcc.ufmg.br

Allen Ibiapina
email: allen.ibiapina@alu.ufc.br

Raul Lopes

Ignasi Sau
email: ignasi.sau@lirmm.fr

Ana Silva
email: anasilva@mat.ufc.br

Coloring Problems on Bipartite Graphs of Small Diameter

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 [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF], 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 [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF], 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 [START_REF] Kratochvíl | On the b-chromatic number of graphs[END_REF].

Mathematics Subject Classifications: 05C15, 68R10, 68Q17

Introduction

Graph coloring problems are among the most fundamental and studied problems in graph theory, due to their practical and theoretical importance. A proper coloring of a graph G is a function f : V (G) → N such that f (u) = f (v) for every edge uv ∈ E(G), and the k-Coloring problem asks whether a given graph G admits a proper coloring using at most k colors. A well-known result by Karp [START_REF] Karp | Reducibility among Combinatorial problems[END_REF] shows that the k-Coloring problem is NP-complete for every fixed k 3. In this paper, we study two of the most general coloring problems: list coloring and graph homomorphism.

In the k-List Coloring problem, we are given a graph G together with a function L which assigns to each u ∈ V (G) a subset of allowed colors with |L(u)| k for every u ∈ V (G). This is called a list assignment of G. The question is whether G admits a proper coloring f such that f (u) ∈ L(u) for every u ∈ V (G); if the answer is yes, we say that G is L-colorable. If G is L-colorable for every list assignment L satisfying |L(v)| k for every v ∈ V (G), we say that G is k-choosable.

Observe that this generalizes the k-Coloring problem: it suffices to consider L(u) = {1, . . . , k} for every u ∈ V (G). Thus k-List Coloring is NP-complete for every fixed k 3; this was shown by Holyer [START_REF] Holyer | The NP-completeness of edge-coloring[END_REF] and Karp [START_REF] Karp | Reducibility among Combinatorial problems[END_REF]. Another natural coloring problem that can be modeled as a list coloring problem is the k-Precoloring Extension problem, where some vertices have fixed colors and the goal is to extend this precoloring to a proper k-coloring of G. Thus we can model this problem as a list coloring problem by assigning a list of size 1 to each of the precolored vertices, and a list equal to {1, . . . , k} to the remaining ones. From now on, we denote this problem by k-PreExt.

A long-standing and still open question about coloring problems is whether one can decide in polynomial time if a graph with diameter two can be properly colored using at most three colors (see e.g. [START_REF] Kamiński | Open problems from algorithmic graph theory[END_REF][START_REF] Paulusma | Open problems on graph coloring for special graph classes[END_REF]), and only recently the answer for the 3-Coloring problem on graphs with diameter at most three has been settled negatively by Mertzios and Spirakis [START_REF] Mertzios | Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs[END_REF]. Here we propose the investigation of analogous questions concerning list colorings of bipartite graphs.

The famous Hajós Theorem [START_REF] Hajós | Über eine konstruktion nicht n-färbbarer graphen[END_REF] states that every non-k-colorable graph can be constructed from the complete graph K k+1 by iteratively applying one of three defined opera-A homomorphism f from a graph G to a graph H is surjective if every vertex x ∈ V (H) is the image of some vertex u ∈ V (G), and it is edge-surjective if every edge xy ∈ E(H) is the image of some edge uv ∈ V (G). Observe that if f is edge-surjective and H has no isolated vertices, then f is also surjective. If H is a subgraph of G and f is an homomorphism from G to H such that f (v) = v for every v ∈ V (H), we say that f is a retraction of G to H. We denote the related problems by Surjective H-Homomorphism, Edge-Surjective H-Homomorphism, and Retract, respectively. Some authors use the term (edge-)compaction to refer to (edge-)surjective homomorphism, but we prefer to use a more descriptive term. Also, if Retract is restricted to instances (G, H) such that H is isomorphic to a fixed graph F , then we write Retract to F to denote the related problem.

Vikas [START_REF] Vikas | Compaction, retraction, and constraint satisfaction[END_REF] showed that problem Surjective H-Homomorphism reduces to Edge-Surjective H-Homomorphism and to Retract to H. Therefore, it follows from the result by Hell and Nešetřil [START_REF] Hell | On the complexity of H -coloring[END_REF] that all three problems are NP-complete when H is not bipartite, as it suffices to add a dummy copy of H to G so as to force the obtained graph G to have a surjective homomorphism to H if and only if G has a homomorphism to H. As for the remaining cases, since the late 1980's there has been interest in the complexity of these problems when H is a bipartite graph, with related questions being posed by many authors (see e.g. [START_REF] Martin | The computational complexity of disconnected cut and 2K 2 -partition[END_REF][START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF]). Let C 4 denote the reflexive cycle on four vertices. Vikas [START_REF] Vikas | Computational complexity of compaction to cycles[END_REF] proved that Edge-Surjective C 4 -Homomorphism is NP-complete, and only recently Surjective C 4 -Homomorphism has been also proved to be NP-complete by Martin and Paulusma [START_REF] Martin | The computational complexity of disconnected cut and 2K 2 -partition[END_REF]. Golovach et al. [START_REF] Golovach | Finding vertex-surjective graph homomorphisms[END_REF] proved that Surjective H-Homomorphism is polynomial when H is a path, and NP-complete for many other cases (e.g. linear forests and trees of pathwidth at most 2). Also, Golovach et al. [START_REF] Golovach | Surjective H-colouring: New hardness results[END_REF] recently proved that Surjective H-Homomorphism is NP-complete when H has exactly 2 vertices u and v such that {uu, vv} ⊆ E(H), provided uv / ∈ E(H). We refer the reader to the nice survey by Bodirsky et al. [START_REF] Bodirsky | The complexity of surjective homomorphism problems -a survey[END_REF] on surjective homomorphisms and related problems. Martin and Paulusma [START_REF] Martin | The computational complexity of disconnected cut and 2K 2 -partition[END_REF] also relate Edge-Surjective H-Homomorphism to many other problems (e.g. vertex cut-sets, H-partitions, and biclique cover), showing that various open problems and Surjective C 4 -Homomorphism, which they prove to be NP-complete, are equivalent.

In particular, the NP-completeness of Retract to C 6 (Feder et al. [START_REF] Feder | List homomorphisms and circular arc graphs[END_REF]), and of Edge-Surjective C 6 -Homomorphism (Vikas [START_REF] Vikas | Computational complexity of compaction to cycles[END_REF]) are known since 1999, but only recently the NP-completeness of Surjective C 6 -Homomorphism has been settled (Vikas [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF]), even though this had been asked by Hell and Nešetřil back in 1988 [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF]. Here we give a stronger NP-completeness result for Retract to C 6 that we then use in some of our proofs. Namely, letting H ∼ = C 6 and G = (X ∪ Y, E) be bipartite, we show that Retract to C 6 is NP-complete even if V (H) ∩ Y dominates X, and each y ∈ V (H) ∩ Y is at distance at most 2 from y , for every y ∈ Y . We then use this result to show that 3-PreExt, Edge-Surjective C 6 -Homomorphism, and Surjective C 6 -Homomorphism are NP-complete even when restricted to bipartite graphs with diameter four. Our NP-completeness proof for Surjective C 6 -Homomorphism produces a smaller graph than the one presented by Vikas [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF], needing only a linear number of new vertices in the construction against a quadratic number used by Vikas [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF], which allows us to present a simpler proof. In addition, we make a small observation that, by letting M k denote the graph obtained from the complete bipartite graph K k,k by removing a perfect matching, we get that Surjective M k -Homomorphism, Edge-Surjective M k -Homomorphism, and Retract to M k are all NP-complete on graphs of diameter three.

Vikas [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF] also points out, without explicitly proving it, that his reduction can be generalized to a proof that Surjective C 2k -Homomorphism is NP-complete for every k 3. Unfortunately, we have not managed to directly adapt our reduction to this case. Finally, we mention that there is still interest in the C k -homomorphism problem for odd k when restricted to P -free graphs because of its ties with the long-standing open problem of 3-coloring P -free graphs (see e.g. a recent paper by Chudnovsky et al. [START_REF] Chudnovsky | Complexity of C k -coloring in hereditary classes of graphs[END_REF]).

Given a graph G, a biclique of G is a pair of vertex subsets (A, B) forming a complete bipartite subgraph of G. The bipartite complement of a bipartite graph G = (A ∪ B, E) is the bipartite graph G B = (A ∪ B, E ) containing the non-edges between A and B. In the k-Biclique problem, the task is to decide whether V (G) can be partitioned into k bicliques. Mohammad et al. [START_REF] Heydari | Computing cross associations for attack graphs and other applications[END_REF] showed that, letting k be part of the input, k-Biclique is NP-complete even when restricted to bipartite graphs. An attempt to show that 3-Biclique is NP-complete on bipartite graphs was presented by Fleischner et al. [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF]. Unfortunately, as we show in Section 6, there is a mistake in their proof. Nevertheless, applying our result for Surjective C 6 -Homomorphism, we get that the 3-Biclique problem is indeed NP-complete on bipartite graphs, even when the bipartite complement of G has diameter four. It is worth mentioning that Martin and Paulusma [START_REF] Martin | The computational complexity of disconnected cut and 2K 2 -partition[END_REF] showed that 2-Biclique is NP-complete on general graphs (with a very technical reduction that uses an abstract algebraic meta-theorem), and that Fleischner et al. [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF] showed that it is polynomial on bipartite graphs. Hence, the NP-completeness of 3-Biclique on bipartite graphs is best possible in terms of k.

We need two more definitions before presenting our last results. Given a proper kcoloring f of a graph G, a vertex v is called a b-vertex if the neighborhood of v contains one vertex of each color (distinct from that of v), and f is a k-fall-coloring of G if every vertex of G is a b-vertex. In the k-Fall Coloring problem, we ask whether an input graph G admits a k-fall-coloring. We show that if 3-Fall Coloring were NP-complete on bipartite graphs with diameter three, then we would get a complete dichotomy for the list coloring problems on bipartite graphs with diameter constraints. Also, this would answer a question posed by Kratochvíl et al. [START_REF] Kratochvíl | On the b-chromatic number of graphs[END_REF]. Although we do not know whether 3-Fall Coloring is NP-complete on bipartite graphs with diameter three, we show that it is NP-complete on bipartite graphs with diameter four, strengthening a result of Laskar and Lyle [START_REF] Laskar | Fall colouring of bipartite graphs and cartesian products of graphs[END_REF]. Organization. In Section 2 we present the formal notation and definitions used in this article. In Section 3 we give an almost complete classification for the investigated list coloring problems in terms of the number of colors and the diameter of the input graph G, taking into account the results presented in the current article. In Section 4 we show our hardness result for Retract to C 6 and use it to prove that 3-PreExt is NP-complete on bipartite graphs with diameter four. In Section 5 we show that Edge-Surjective C 6 -Homomorphism and Surjective C 6 -Homomorphism are NP-complete on bipartite graphs with diameter four. In Section 6, we point out the flaw in the hardness proof for 3-Biclique on bipartite graphs presented by Fleischner et al. [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF], and show how to obtain the result using the results presented in Section 5. Finally, in Section 7 we provide a reduction from 3-Fall Coloring to 3-PreExt that preserves the diameter of the input graph, and prove that 3-Fall Coloring is NP-complete on bipartite graphs with diameter four.

Definitions and notation

All graphs that we consider are simple, that is, they do not have loops nor multiple edges. We can also assume that the graphs are connected, as otherwise it suffices to solve the problems on the connected components. For basic definitions on graph theory, we refer the reader to [START_REF] West | Introduction to graph theory[END_REF].

For u, v ∈ V (G), we denote by dist(u, v) the length of a shortest path between u v, and it is called the distance between u and v in G. The diameter of a graph G is the maximum distance between any pair of vertices of G. We denote by B the class of bipartite graphs. Also, for a fixed positive integer d, we denote by B d the class of bipartite graphs with diameter at most d, and by D d the class of graphs with diameter at most d. A set

X ⊆ V (G) is a dominating set of G if every vertex of G is either in X or has a neighbor in X. Similarly, we say that A ⊆ V (G) dominates B ⊆ V (G) if every vertex of B is either in A or has a neighbor in A. For a graph H ⊆ G, we denote by N H (v) the set of neighbors of v that are contained in V (H).
For an integer 1, we denote by [ ] the set {1, . . . , }. Given problems P and P , we write P P to denote that there exists a polynomial reduction from P to P (hence, P is at least as hard as P ). Also, given a graph class G and a problem P , we denote P restricted to G by P | G . Given sets A and B, a function f : A → B, and an element b ∈ B, the set of elements of A whose image is b is denoted by f -1 (b). Also, given X ⊆ A, we denote the image of X by f (X), i.e., f (X) = {f (x) | x ∈ X}. If f (X) = {b}, we abuse notation and write f (X) = b.

Given a graph G and a positive integer k, we say that a function f :

V (G) → [k] is a proper k-coloring of G if f (u) = f (v) for every uv ∈ E(G). A vertex v is called a b-vertex if f (N [v]) = [k], and f is a k-fall-coloring of G if every vertex of G is a b-vertex. A list assignment of G is a function L : V (G) → 2 N that assigns to each vertex u ∈ V (G) a finite subset L(u) of positive integers. A partial k-coloring of G is a function p : V → [k]
where V ⊆ V (G) and p is a proper coloring of the subgraph of G induced by V . If V is not given, we denote it by dom(p). Given a partial k-coloring p of G, we say that

f is a k-extension of p if f is a proper k-coloring of G such that f (u) = p(u) for every u ∈ dom(p).
A biclique of a graph G is a pair of vertex non-empty subsets (A, B) such that G = (A ∪ B, E ) is a complete bipartite graph, where G is the subgraph of G with vertex set A∪B, and edge set E containing the edges of G between A and

B. A k-biclique partition of G is a set of k disjoint bicliques {(A 1 , B 1 ), • • • , (A k , B k )} such that k i=1 (A i ∪ B i ) = V (G)
. The coloring problems investigated in this article are formally defined below, adopting the notation from other papers; see e.g. [START_REF] Paulusma | Open problems on graph coloring for special graph classes[END_REF]. In each of the problems defined below, we consider k to be a fixed integer with k 1.

k-List Coloring Input:

A graph G = (V, E) and a list assignment L s.t.

|L(u)| k for every u ∈ V (G). Question: Does G admit a proper coloring f s.t. f (u) ∈ L(u) for every u ∈ V (G)? List k-Coloring Input: A graph G = (V, E) and a list assignment L s.t. L(u) ⊆ [k] for every u ∈ V (G). Question: Does G admit a proper coloring f s.t. f (u) ∈ L(u) for every u ∈ V (G)? k-PreExt Input:
A graph G = (V, E), a positive integer k, and a partial k-coloring p of G.

Question: Does p have a k-extension? k-Biclique Partition Input: A graph G = (V, E). Question: Does G have a k-biclique partition? k-Fall-Coloring Input:
A graph G = (V, E). Question: Does G admit a k-fall-coloring?

The investigated homomorphism problems are listed below, where H is considered to be a fixed graph whenever it is part of the name of a problem.

Surjective H-Homomorphism Input:

A graph G = (V, E). Question: Does G have a surjective homomorphism to H?

Edge-Surjective H-Homomorphism Input:

A graph G = (V, E). Question: Does G admit an edge-surjective H-homomorphism?

Retract

Input:

A graph G = (V, E) and a subgraph F ⊆ G. Question: Is there a retraction of G to F ?

Retract to H Input:

A graph G = (V, E) and a subgraph F ⊆ G isomorphic to H. Question: Is there a retraction of G to F ? A 3-uniform hypergraph is a hypergraph such that each hyperedge has size exactly 3. A 2-coloring of a hypergraph G is a function f : V (G) → {1, 2} such that f (e) = {1, 2} for every hyperedge e ∈ E(G) (i.e., no hyperedge is monochromatic). Lovász [START_REF] Lovász | Coverings and colorings of hypergraphs[END_REF] showed that the problem of 2-coloring 3-uniform hypergraphs, formally defined below, is NP-complete. This problem will be used in the reductions of Sections 4 and 7.

3-Uniform Hypergraph 2-Coloring (abbreviated as 3-Uniform 2-Col)

Input: A 3-uniform hypergraph G = (V, E). Question: Does G admit a 2-coloring?
From here on, we let n denote the number of vertices of the input graph of the problem under consideration.

List coloring vs. diameter

In this section, we investigate the complexity of k-PreExt, List k-Coloring, and k-List Coloring on bipartite graphs with diameter d, for a fixed integer d 2. We provide a complete picture about the hardness of these problems, leaving as open cases only 3-PreExt and List 3-Coloring for d = 3.

First, notice that there is a straightforward reduction from k-PreExt to List k-

Coloring. Indeed, for each v ∈ V (G), if v is precolored with color p(v), then define L(v) = {p(v)}; otherwise, define L(v) = [k]. Furthermore, List k-Coloring is a partic- ular case of k-List
Coloring, since each vertex in an instance of the former problem has a list assignment of size at most k. From these two remarks, we get

k-PreExt List k-Coloring k-List Coloring. (1)
Since the reductions discussed above do not change the input graph, we get that Equation (1) holds when we restrict the problems to graphs in B d . We remark that there are polynomial-time algorithms for the 2-List Coloring problem by Lovász [START_REF] Lovász | Coverings and colorings of hypergraphs[END_REF] and Vizing [START_REF] Vadim | Coloring the vertices of a graph in prescribed colors[END_REF], and hence for 2-PreExt and List 2-Coloring as well. In what follows we focus on the complexity of these problems for k 3. Observe that if k-PreExt is proved to be NP-complete on bipartite graphs for some k, then the same holds for the other problems, and the next result shows that it also implies that (k + 1)-

PreExt| B 3 is NP-complete. Proposition 1. Let k 1 be a fixed integer. Then k-PreExt| B (k + 1)-PreExt| B 3 .
Proof. Let G ∈ B with parts X and Y , p be a partial k-coloring of G, and (G , p ) be an instance of (k + 1)-PreExt| B 3 obtained from (G, p) as follows. To obtain G , add to G two new vertices x and y, all edges from x to vertices in Y , and all edges from y to vertices in X; therefore G is a bipartite graph with parts X = X ∪ {x} and

Y = Y ∪ {y}. Let p Diameter 3-PreExt List 3-Coloring 3-List Coloring 2 P P [18, 5] NP-c [19] 3 open open NP-c 4 NP-c (Sec. 4) NP-c NP-c
Table 1: Row labeled i presents the complexity of the corresponding problems restricted to bipartite graphs with diameter at most i. Let us argue about the diameter of G . Recall that we can assume that G is connected, and therefore it has no isolated vertices. Consider a pair u, v ∈ V (G ). If they are within the same part, say X , then either they are both adjacent to y, or u = x in which case (x, w, v) is a path, where w is any neighbor of v in Y (recall that G has no isolated vertices). If u ∈ X and v ∈ Y , then either {u, v} ∩ {x, y} = ∅, in which case (u, y, w, v) is a (u, v)-path for any neighbor w of v with w ∈ X; or {u, v} = {x, y} and (x, w, w , y) is a (u, v)-path for any edge ww ∈ E(G); or |{u, v} ∩ {x, y}| = 1, in which case uv ∈ E(G ). Thus, we get that G has indeed diameter at most 3.

Diameter k-PreExt List k-Coloring k-List Coloring 2 P P [18, 5] NP-c 3 NP-c (Prop. 1) NP-c NP-c 4 NP-c NP-c NP-c
Table 1 (resp. Table 2) presents the complexity of the problems discussed in this section for k = 3 (resp. for every fixed k 4) restricted to bipartite graphs with diameter at most 2, 3, and 4. Let us explain how these tables are filled. In Section 4 we prove that 3-PreExt| B 4 is NP-complete. Note that, from Equation (1) and the fact that B d ⊆ B d+1 , we get that the forth row downwards in Table 1 is filled with NP-completeness results. Also, by Proposition 1, we get that for every fixed k 4, row 3 downwards in Table 2 is filled with NP-completeness results. When G is a complete bipartite graph, the polynomiality of List k-Coloring and k-PreExt follows from previous results by Couturier et al. [START_REF] Couturier | List coloring in the absence of a linear forest[END_REF] and Hoàng et al. [START_REF] Chính | Deciding k-colorability of P 5 -free graphs in polynomial time[END_REF]. In Section 3.1, we briefly discuss those results and show a simple algorithm for List k-Coloring that is better than both when the input graph is a complete bipartite graph. Finally, Jansen and Scheffler [START_REF] Jansen | Generalized coloring for tree-like graphs[END_REF] proved that 3-List Coloring is NP-complete on complete bipartite graphs. The last two sentences justify the second row of both tables.

List k-Coloring is polynomial on complete bipartite graphs

We begin this section by discussing some previously known results for List k-Coloring. For r 1, let rH denote the graph formed by r disjoint copies of a graph H, and by G + H we denote the graph formed by the disjoint union of the graphs G and H.

Hoàng et al. [START_REF] Chính | Deciding k-colorability of P 5 -free graphs in polynomial time[END_REF] considered the List k-Coloring problem in P 5 -free graphs. A key ingredient of their algorithm is a result by Bacsó and Tuza [START_REF] Bacsó | Dominating cliques in P 5 -free graphs[END_REF] stating that every P 5 -free graph contains a dominating structure, that is, an induced subgraph D ⊆ G that is isomorphic to P 3 or to a complete graph, and V (D) is a dominating set of G. Their algorithm starts by performing a brute-force search for a dominating structure D of size at most k over all n k sets of vertices of size k in G. If none is found, then by the aforementioned result by Bacsó and Tuza [START_REF] Bacsó | Dominating cliques in P 5 -free graphs[END_REF], G contains a clique of size at least k + 1 and thus it is not k-colorable. Otherwise, they guess a coloring of D and reduce the original List k-Coloring instance to solving at most (kn) k 5 instances of List (k-1)-Coloring, which are then solved recursively.

Couturier et al. [START_REF] Couturier | List coloring in the absence of a linear forest[END_REF] generalized the result by Hoàng et al. [START_REF] Chính | Deciding k-colorability of P 5 -free graphs in polynomial time[END_REF] to (rP 1 +P 5 )-free graphs. They showed that any such graph that is L-colorable, where L is a list assignment of G with L(u) ⊆ [k] for every u ∈ V (G), admits another kind of dominating set of size at most f (k), for some computable function f , and their algorithm for List k-Coloring also depends on finding a dominating set of size at most f (k) in G and on solving O(n f (k) ) new instances.

We provide a simple algorithm for List k-Coloring in complete bipartite graphs that has the advantage of being an FPT algorithm, while the algorithms discussed above are clearly XP. As mentioned before, this algorithm also solves k-PreExt on complete bipartite graphs, by Equation ( 1) and the fact that the reduction does not modify the input graph.

Theorem 2. The List k-Coloring| B 2 problem can be solved in time O(2 k • k • log k • n).
In particular, it can be solved in linear time for every fixed integer k 1. In fact, Theorem 2 states that List k-Coloring| B 2 is fixed-parameter tractable parameterized by k, using terminology from parameterized complexity (cf. for instance [START_REF] Cygan | Parameterized Algorithms[END_REF]).

On the other hand, by considering the disjoint union of instances of List k-Coloring| B 2 it is easy to obtain a so-called and-cross-composition (see again [START_REF] Cygan | Parameterized Algorithms[END_REF]), hence refuting, under standard complexity assumptions, the existence of polynomial kernels for the problem List k-Coloring, parameterized by k, restricted to the graph class consisting of the disjoint union of complete bipartite graphs. Note that List k-Coloring restricted to this class is also fixed-parameter tractable, since one can solve the problem independently on each connected component. We leave as an open problem the existence of a polynomial kernel for List k-Coloring| B 2 parameterized by k.

Retract to C 6

Our goal is to show that Retract to C 6 is NP-complete even under various constraints, which imply that the input graph is in B 4 . These constraints shall be particularly useful in the next section, where we prove the NP-completeness of Edge-Surjective C 6 -Homomorphism and Surjective C 6 -Homomorphism on B 4 . The proof of the following theorem consists of an appropriate modification of a reduction by Kratochvíl [START_REF] Kratochvíl | Precoloring extension with fixed color bound[END_REF]. Basically, we start from the 3-Uniform 2-Col problem, instead of 1-in-3 SAT, which allows us to combine a small gadget introduced by Kratochvíl (called AB-link) in a unique edge-gadget (instead, Kratochvíl had to combine them in eight distinct ways, depending on whether each variable was positive or negative). Additionally, since we do not need planarity, we can start with only six pre-colored vertices, which allows us to bound the diameter of G. Proof. We reduce from the 3-Uniform 2-Col problem (recall the definition from Section 2). For this, consider a 3-uniform hypergraph H = (V, E), and let G be the bipartite graph with bipartition (V, E) such that ue ∈ E(G) if and only if u ∈ e. Add vertices p

V 1 , p V 2 , p V 3 and p E 1 , p E 2 , p E
3 to parts V and E, respectively, and make the subgraph induced by these vertices be the cycle

C = (p V 1 , p E 2 , p V 3 , p E 1 , p V 2 , p E 3 , p V 1 )
. Add an edge between each v ∈ V and p E 3 . This ensures that any retraction f from

G to C is such that f (V ) = {p V 1 , p V 2 } = N C (p E 3
). Now, for each hyperedge e ∈ E, we replace some of the edges incident to e with an edge gadget defined as follows. For easier reference, let V = {v 1 , . . . , v n } and E = {e 1 , . . . , e m }. Let e j ∈ E, and let i 1 , i 2 , i 3 be the indices of the vertices within e j . Remove edges v i 1 e j and v i 2 e j from G, and replace them with the gadget of Figure 1. For better visibility, sometimes we make more than one copy of some of the vertices of C in the figure (for instance, vertex p E 3 is represented 3 different times, but all occurrences correspond to the same vertex). Dashed and solid vertices are used to represent the bipartition of G. The purpose of this gadget is to ensure that hyperedge e j cannot be monochromatic, as discussed below.

We need to prove that G is a bipartite graph, that C has the desired properties, and that f has a retraction to C if and only if H has an appropriate 2-coloring. We first prove

e j v 1,j v 1,j v i 1 d 1,j c 1,j b 1,j a 1,j p E 2 p V 2 p V 1 p V 1 p E 1 p V 3 p E 3 v 2,j v 2,j v i 2 d 2,j c 2,j b 2,j a 2,j p E 1 p V 1 p V 2 p V 2 p E 2 p V 3 p E 3 v i 3 p E 3 Figure 1: Gadget for hyperedge e j = {v i 1 , v i 2 , v i 3 }.
the latter. So, let f be a retraction to C; we prove that f restricted to V is a 2-coloring, using colors p V 1 , p V 2 , such that no hyperedge is monochromatic. Suppose otherwise and let

e j = {v i 1 , v i 2 , v i 3 } be such that f ({v i 1 , v i 2 , v i 3 }) is monochromatic. Because every vertex in V is adjacent to p E 3 , we get that f ({v i 1 , v i 2 , v i 3 }) ∈ {p V 1 , p V 2 } = N C (p E 3 ). First, suppose that f ({v i 1 , v i 2 , v i 3 }) = p V 1 .
We prove that f must be as depicted in Figure 2, a contradiction since in this case e j has neighbors in f -1 (p E i ) for every i ∈ [START_REF] Bodirsky | The complexity of surjective homomorphism problems -a survey[END_REF], and therefore cannot be mapped to C. Labels of vertices that do not have their image forced are left blank. Note that C can also be seen as the complete bipartite graph minus the perfect matching {p

V i p E i | i ∈ [3]}. Because a 1,j is adjacent to p V 3 and to v i 1 ∈ f -1 (p V 1 ), we get that f (a 1,j ) = p E 2 .
But now we get that v 1,j is adjacent to p E 1 and to f -1 (p E 2 ), and therefore must be in p V 3 . This implies that d 1,j is adjacent to p V 2 and f -1 (p V 3 ), and hence is colored with p E 1 . Finally, we get that v 1,j is adjacent to p E 2 and f -1 (p E 1 ), and must be colored with p V 3 . The analysis for the right-hand side of the gadget is similar. For the case where

f ({v i 1 , v i 2 , v i 3 }) = p V 2 ,
we have the situation depicted in Figure 3, and it follows similarly. Therefore, no edge is monochromatic, as we wanted to prove.

Conversely, suppose now that f is a 2-coloring of H with no monochromatic hyperedge, and let f be obtained from f by mapping to p V i all the vertices colored with i, for i ∈ {1, 2}. Let e j = {v i 1 , v i 2 , v i 3 }. We show how to map the vertices within the hyperedge gadget related to e j . The possibilities are the following:

• f (v i 1 ) = f (v i 2 ) = p V 1 : in this case f (v i 3 ) = p V
2 since e j is not monochromatic. Map the vertices as in Figure 2, except for v i 3 , and note that we can map e j to p E 1 , and that the blank vertices can be mapped to C;

• f (v i 1 ) = f (v i 2 ) = p V 2 : in this case f (v i 3 ) = p V
1 since e j is not monochromatic. Map the vertices as in Figure 3, except for v i 3 , and note that e j can be mapped to p V 2 , and that the blank vertices can be mapped to C;

• f (v i 1 ) = p V 1 and f (v i 2 ) = p V 2 :
map the left-hand side as in Figure 2, and the righthand side as in Figure 3. Note that e j can be mapped to p

∈ {p E 1 , p E 2 } \ {f (v i 3 )},
the electronic journal of combinatorics 28(2) (2021), #P2.14

e j p V 3 v 1,j p V 3 v 1,j p V 1 v i 1 p E 1 d 1,j p E 2 a 1,j p E 2 p V 2 p V 1 p V 1 p E 1 p V 3 p E 3 p V 2 v 2,j p V 1 v 2,j p V 1 v i 2 p E 3 c 2,j p E 3 b 2,j p E 1 p V 1 p V 2 p V 2 p E 2 p V 3 p E 3 p V 1 v i 3 p E 3 Figure 2: Coloring of a hyperedge gadget when f ({v i 1 , v i 2 , v i 3 }) = p V 1 . Vertices v i 1 , v i 2 ,
and v i 3 are emphasized. The image of a vertex is put inside of the node, and its label appears next to it, with the exception of e j . Note that the blank vertices can be colored, from left to right, with p E 2 , p E 2 , p E 3 , and p E 2 .

and that the blank vertices can be mapped to C;

• f (v i 1 ) = p V 2 and f (v i 2 ) = p V 1 :
map the left-hand side as in Figure 3, and the righthand side as in Figure 2. Note that e j can be mapped to p E 3 , and that the blank vertices can be mapped to C.

Finally, we need to prove that G is bipartite, and that C has the desired properties. To see that G is bipartite, just observe that the dashed and solid vertices in Figure 1 form a bipartition of G; let (X, Y ) be such a bipartition, where V ⊆ X and E ⊆ Y (i.e., X contains the dashed vertices, and Y the solid ones). More formally, one can see that

X = V ∪ {p V 1 , p V 2 , p V 3 } ∪ {v i,j , v i,j | i ∈ [2], j ∈ [m]}; Y = E ∪ {p E 1 , p E 2 , p E 3 } ∪ {a i,j , b i,j , c i,j , d i,j | i ∈ [2], j ∈ [m]}.
As for the properties of C, observe first that every x ∈ X is adjacent to p E i , for some i ∈ {1, 2, 3}, i.e., Y C = {p E 1 , p E 2 , p E 3 } dominates X. It remains to prove that every p ∈ Y C is at distance at most 2 from every y ∈ Y . Given e j ∈ E, denote by Y j the subset of vertices in Y contained in a gadget related to e j ; hence Y = Y C ∪ j∈[m] Y j and it suffices to prove that, given some j ∈ [m], every p ∈ Y C is at distance at most 2 from every vertex in Y j . For p E 1 , it follows from the fact that

Y j ⊆ N ({v 1,j , v 2,j , p V 2 , p V 3 }) and that {v 1,j , v 2,j , p V 2 , p V 3 } ⊆ N (p E 1 ). For p E 2 , if follows from the fact that Y j ⊆ N ({v 2,j , v 1,j , p V 1 , p V 3 }) and that {v 2,j , v 1,j , p V 1 , p V 3 } ⊆ N (p E 2 ). Finally, for p E 3 if follows from the fact that Y j ⊆ N ({v i 1 , v i 2 , v i 3 , p V 1 , p V 2 }) and that {v i 1 , v i 2 , v i 3 , p V 1 , p V 2 } ⊆ N (p E
3 ). Corollary 4. 3-PreExt| B 4 is NP-complete, even if every vertex in one of the parts is adjacent to some precolored vertex. 4. For this, first we argue that dist(x, y) 3 for every x ∈ X and y ∈ Y ; indeed, either xy ∈ E(G) or (x, p E i , w, y) is a path between x and y, where p E i is any vertex in N (x) ∩ C and (p E i , w, y) is the (p E i , y)-path of length 2 ensured in the statement of Theorem 3. Now, for x, x ∈ X, let y ∈ N (x) (it exists by construction); we know from the previous sentence that dist(y, x ) 3 and thus it follows that dist(x, x ) 4. The argument for y, y ∈ Y is symmetric.

e j p V 1 v 1,j p V 2 v 1,j p V 2 v i 1 p E 3 c 1,j p E 3 b 1,j p E 2 p V 2 p V 1 p V 1 p E 1 p V 3 p E 3 p V 3 v 2,j p V 3 v 2,j p V 2 v i 2 p E 2 d 2,j p E 1 a 2,j p E 1 p V 1 p V 2 p V 2 p E 2 p V 3 p E 3 p V 2 v i 3 p E 3 Figure 3: Coloring of a hyperedge gadget when f ({v i 1 , v i 2 , v i 3 }) = p V 2 . Vertices v i 1 , v i 2 ,

Surjective C 6 -homomorphism

We first prove that Edge-Surjective C 6 -Homomorphism is NP-complete on B 4 , and as a byproduct we get that Surjective C 6 -homomorphism is NP-complete (cf. Corollary 7). Notice that, unlike in the retraction problem, in the Edge-Surjective C 6 -Homomorphism problem, the target C 6 is not necessarily a fixed subgraph of G. However, we show that, under some assumptions, an edge surjective C 6 -homomorphism for G coincides with a retraction of G to H for some choice of H ⊆ G such that H ∼ = C 6 . We remark that another proof that Edge-Surjective C 6 -Homomorphism is NP-complete was given by Vikas [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF]. However, our proof is simpler and we consider constraints which are not present in the proof of Vikas [START_REF] Vikas | Computational complexity of graph partition under vertexcompaction to an irreflexive hexagon[END_REF].

In what follows, we present a reduction from Retract to C 6 on bipartite graphs of diameter four to Edge-Surjective C 6 -Homomorphism. Let G and H be the input graph and subgraph, respectively; also, let us write H as (h 1 , . . . , h 6 ), and X, Y be the parts of G, with {h 1 , h 3 , h 5 } ⊆ Y . We first introduce the gadget depicted in Figure 4 related to a vertex u ∈ Y \ V (H). The cycle (h 1 , . . . , h 6 ) represents a circular permutation of (h 1 , . . . , h 6 ) such that h 1 ∈ {h 1 , h 3 , h 5 }; we call this the (h 1 , h 4 )-gadget (this is because h 1 h 4 is the diagonal related to this gadget). We obtain the input graph G of Surjective C 6 -homomorphism from G by adding an (h 1 , h 4 )-gadget related to each u ∈ Y \ V (H), for each possible pair (h 1 , h 4 ) such that h 1 ∈ {h 1 , h 3 , h 5 }, namely for (h 1 , h 4 ), (h 3 , h 6 ), and (h 5 , h 2 ) (see Figure 6). Note that V (G ) \ V (G) consists of precisely the vertices {a, b, c, d, e, g} introduced for each choice of u ∈ Y \ V (H) and each choice of h 1 , for a total of 6(|Y | -3) new vertices. We use the circular permutation in the following lemma to avoid making analogous arguments for each type of gadget separately. Lemma 5. Let G ∈ B 4 and H ⊆ G be isomorphic to a C 6 ; write H = (h 1 , . . . , h 6 ). Also, let G be obtained from G by adding the gadget represented in Figure 4 for every u ∈ X, and every (h 1 , h 4 ) ∈ {(h 1 , h 4 ), (h 3 , h 6 ), (h 5 , h 2 )}. Let f be an edge-surjective C 6 -homomorphism of G to the C 6 (1, . . . , 6). Suppose that (h 1 , . . . , h 6 ) is a circular permutation of H such that h 1 ∈ {h 1 , h 3 , h 5 }, and f

(h i ) = i for each i ∈ {3, 4, 5}. If some u ∈ V (G) \ V (H) is such that f (u) = 1, then f is a retraction of G to H. Proof. We prove that if there exists a vertex u ∈ V (G) \ V (H) such that f (u) = 1, then f (h 1 ) = 1; note that the lemma follows since {1, 3} = {f (h 1 ), f (h 3 )} ⊆ N (f (h 2 )), and {1, 5} = {f (h 1 ), f (h 5 )} ⊆ N (f (h 2 )) imply that f (h 2 ) = 2 and f (h 6 ) = 6.
To see that f (h 1 ) = 1, note that the images of the gadget related to u must be as depicted in Figure 5, as explained next (fixed values appear inside the vertex, while implied values appear between parenthesis next to the vertex). Since g is adjacent to u ∈ f -1 (1) and h 5 ∈ f -1 (5), we get that f (g) = 6. Similarly, we get f (c) = 2 since it is adjacent to u ∈ f -1 (1) and h 3 ∈ f -1 (3). Note that this implies that f (d) = 3 and f (e) = 5, which in turn implies that f (a) = 6 and f (b) = 2. Because a, b ∈ N (h 1 ), we get f (h 1 ) = 1 as we wanted to prove.

h 1 (1) h 2 h 6 3 h 3 4 h 4 5 h 5 a (6) b(2) c(2) d(3)
e( 5) g( 6)

1 u Figure 5: Mapping of a diagonal gadget related to u ∈ X such that f (u) = 1, when f (h i ) = i for each i ∈ {3, 4, 5}. We get that f (h 1 ) = 1.
Recall that Theorem 3 states that the restriction of Retract to C 6 used in the following lemma is NP-complete. Lemma 6. Let G = (X∪Y, E) be a bipartite graph and H ⊆ G be a subgraph isomorphic to C 6 . Let Y H be the set V (H) ∩ Y , and suppose that Y H dominates X and that dist(h, y) 2 for every h ∈ Y H and y ∈ Y . If G is obtained as in Lemma 5, then G is a bipartite graph with diam(G ) 4, and the answer to the Retract to C 6 instance is yes if and only if the answer to G admits an edge-surjective homomorphism to C 6 .

Proof. Write H as before and suppose Y H = {h 1 , h 3 , h 5 }. Denote by A, B, C the sets of vertices containing the vertices labeled with a, b, c in the gadgets depicted in Figure 6, respectively. To see that G is bipartite, observe the coloring in grey and black in Figure 6, with Y being gray. Now, denote by (X , Y ) the bipartition of G such that X ⊆ X , and observe that X = X ∪B ∪C and Y = Y ∪A. We prove that the same property holding for Y H in G also holds in G . The fact that diam(G ) 4 then follows by the same argument given in Corollary 4. We discuss each property separately:

1. Y H dominates X : we know that Y H dominates X by assumption. Also, one can verify in Figure 6 that every vertex in B∪C is adjacent to some vertex in {h 1 , h 3 , h 5 };

2. dist(h, y) 2 for every y ∈ Y and h ∈ Y H : we know that this holds when y ∈ Y by assumption. Consider a vertex a ∈ A. It suffices to show that this holds when a is within an (h 1 , h 4 )-gadget, since the other cases are symmetric. So let u be such that a is within the (h 1 , h 4 )-gadget related to u. If a = a u 1,1,4 , then (a, b u 1,1,4 , h 1 ), (a, c u 1,1,4 , h 3 ), and (a, h 4 , h 5 )) are paths of length 2 between a and each h ∈ {h 1 , h 3 , h 5 }, as we wanted to show. An analogous argument holds if a = a u 2,1,4 . Now, we prove the second part of the theorem. Let f be a retraction of G to H. Since H is isomorphic to C 6 , it suffices to extend f to G . Also, because the gadgets are symmetric, we just need to show how to extend f to an (h 1 , h 4 )-gadget. So consider any u ∈ Y . Figure 5 tells us how to extend f to the (h 1 , h 4 )-gadget related to u when f (u) = h 1 (considering h 1 = h 1 ), while Figure 7 shows how to do it when f (u) ∈ {h 3 , h 5 }.

h 2 h 4 h 6 h 1 h 3 h 5 b u 2,1,4 b u 1,1,4 c u 1,1,4 a u 1,1,4 a u 2,1,4 c u 2,1,4 u∈Y (h 1 , h 4 )-gadget h 2 h 4 h 6 h 1 h 3 h 5 a u 1,3,6 a u 2,3,6 b u 1,3,6 b u 2,3,6 c u 1,3,6 c u 2,3,6 u∈Y (h 3 , h 6 )-gadget h 2 h 4 h 6 h 1 h 3 h 5 a u 1,5,2 a u 2,
Because u ∈ Y and {h 2 , h 4 , h 6 } ⊆ X, these are the only options.

Conversely, suppose that G has an edge-surjective C 6 -homomorphism f , and write the target C 6 as H = (1, . . . , 6). We want to prove that f (h i ) = i, for every i ∈ [START_REF] Cygan | Parameterized Algorithms[END_REF], so that f also gives a retraction of G to H. Note that if, at some point, we get that f (h i ) = i either for every odd i, or for every even i, then we are done.

First, we prove that |f (Y H )| > 1. So suppose without loss of generality that f (Y H ) = 1, and note that in this case f (H) ⊆ {1, 2, 6}. Because G is bipartite and f is also vertexsurjective, we know that f -1 (4) = ∅, and since f -1 (4) ⊆ X we get a contradiction to Property (1) of the set Y H , since X would not be dominated by Y H . We then may assume that |f (Y H )| = 2, since the proof is finished when it is equal to 3. This means that 2 vertices among {h 1 , h 3 , h 5 } get distinct images. By relabeling H if necessary, we can assume that the possible cases are the following:

• f (h 3 ) = 3 and f (h 5 ) = 5: this implies that f (h 4 ) = 4. We know by Lemma 5 that f -1 (1) ∩ Y = ∅ as otherwise f (h 1 ) = 1 and the lemma follows. Also, note that {h 2 , h 4 , h 6 } dominates A. Hence, since ∅ = f -1 (1) ⊆ A, we must get that either f (h 2 ) = 2 or f (h 6 ) = 6. In fact, if we get that f (h 2 ) = 2, then by relabeling (1, . . . , 6) to [START_REF] Bodirsky | The complexity of surjective homomorphism problems -a survey[END_REF][START_REF] Chudnovsky | Complexity of C k -coloring in hereditary classes of graphs[END_REF][START_REF] Couturier | List coloring in the absence of a linear forest[END_REF][START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Alon | Colorings and orientations of graphs[END_REF][START_REF] Bacsó | Dominating cliques in P 5 -free graphs[END_REF] and doing the same with H, we get the situation f (h i ) = i for each i ∈ {3, 4, 5, 6}. So suppose this is the case and note that we can assume that f (h 1 ) = 5 and f (h 2 ) = 4, since if f (h 1 ) = 1 and f (h 2 ) = 2 the proof is complete. We want to prove that f -1 (1) = ∅, thus getting a contradiction. Recall that f -1 (1) ⊆ A, and let a ∈ A be such that f (a) = 1. Also let u ∈ Y be such that a is within some diagonal gadget related to u. Observe that a is not within an (h 1 , h 4 )-gadget since {a u 1,1,4 , a u 2,1,4 } ⊆ N (h 4 ), nor within an (h 5 , h 2 )-gadget since {a u 1,5,2 , a u 2,5,2 } ⊆ N (h 2 ), and f (h 2 ) = f (h 4 ) = 4. Therefore, a is within an (h 3 , h 6 )-gadget. The following argument is illustrated in Figure 8. • f (h 1 ) = 1 and f (h 3 ) = 3: an argument analogous to the previous case yields a similar contradiction;

h 1 h 2 h 6 h 3 h 4 h 5 (h 2 ) (h 2 ) (h 2 /h 4 ) (h 3 ) (h 3 ) (h 4 ) h 3 u h 1 h 2 h 6 h 3 h 4 h 5 (h 6 ) (h 6 ) (h 4 ) (h 5 ) (h 5 ) (h 4 /h 6 ) h 5 u
• f (h 1 ) = 1 and f (h 5 ) = 5: again, an analogous argument concludes the proof.

As a direct consequence of Theorem 3 and Lemma 6, we get that Edge-Surjective C 6 -Homomorphism is NP-complete even when G has diameter four. We next argue that this also implies the NP-completeness of Surjective C 6 -Homomorphism. Proof. Let G be a bipartite graph with diameter at most four. The first statement follows by Theorem 3 and Lemma 6. We argue that G has an edge-surjective C 6homomorphism if and only G has a surjective C 6 -homomorphism. Clearly an edgesurjective C 6 -homomorphism is a surjective C 6 -homomorphism, so it remains to show that given a surjective C 6 -homomorphism f of G, it follows that f is an edge-surjective C 6homomorphism as well. Suppose otherwise, and denote the target C 6 by (1, . . . , 6). Without loss of generality, suppose that edge 12 has no pre-image, i.e., there is no uv ∈ E(G) such that f (u) = 1 and f (v) = 2. This means that every path between u ∈ f -1 (1) and v ∈ f -1 (2) is mapped to (1, 6, 5, 4, 3, 2), which implies that dist(u, v) 5, contradicting the hypothesis that diam(G) 4.

Finally, by applying a trick similar to the one used in Proposition 1, we get that:

Corollary 8. For an integer k 4, let M k denote the complete bipartite graph K k,k minus a perfect matching. Also, let G ∈ B 3 and H ⊆ G such that H ∼ = M k . Then Surjective M k -Homomorphism, Edge-Surjective M k -Homomorphism, and Retract to M k are all NP-complete.

3-Biclique Partition on bipartite graphs with diameter four

In this section we first show how Corollary 7 implies the NP-completeness of the 3-Biclique Partition problem, and then we present the flaw in the proof in [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF]. Recall that G B denotes the bipartite complement of G.

Corollary 9. Let G be a bipartite graph such that G B has diameter at most four. Then, deciding whether G has a 3-biclique partition is NP-complete.

Proposition 11. Let k 3 be a fixed positive integer. Then,

k-Fall-Coloring| B (k + 1)-Fall-Coloring| B 3 .
Proof. Let G ∈ B with parts X and Y , and G be obtained from G by adding new vertices x, y together with all edges from x to vertices in Y and all edges from y to vertices in X. This is the same graph as the one constructed in Proposition 1, and thus we already know that G has diameter at most three. Now, we prove that G has a k-fall-coloring if and only if G has a (k + 1)-fall-coloring. If f is a k-fall-coloring of G, then let f be obtained from f by coloring x and y with color k + 1. Every vertex of X and Y is adjacent to the new color, so they continue to be b-vertices, and x and y are b-vertices by Lemma 10. Now, let f be a (k + 1)-fall-coloring of G , and suppose without loss of generality that f (x) = k + 1. Again, by Lemma 10 we get that each part must contain every color. Therefore, because x is complete to Y , we get that the only vertex on Y ∪ {y} that can be colored with k + 1 is y, i.e., f (y) = k + 1. In this case, one can see that f restricted to G must define a k-fall-coloring of G.

We get the following partial classification of the problem. As we already mentioned, the only open case is when k = 3 and d = 3. Proof. Observe that if G is a complete bipartite graph, i.e., a bipartite graph with diameter two, then every coloring that uses more than 2 colors will have a non-b-vertex, hence the answer to k-Fall-Coloring is trivially no when k 3 and G is a complete bipartite graph (that is, d = 2). When k 2, then either G has an isolated vertex and the answer is no, or it does not and the answer is yes since any 2-coloring is also a 2-fall-coloring. For k 4, it is known that 3-Fall-Coloring is NP-complete on bipartite graphs [START_REF] Laskar | Fall colouring of bipartite graphs and cartesian products of graphs[END_REF], which applying Proposition 11 and induction on k gives us that k-Fall-Coloring| B d is also NP-complete for every d 3. For the remaining case, we prove in Theorem 14 that 3-Fall-Coloring| B 4 is NP-complete.

Before we move on to the proof of the case k = 3 and d = 4, we prove the following result.

Proposition 13. 3-Fall-Coloring| B 3 3-PreExt| B 3 .
Proof. We present a Turing reduction from 3-Fall-Coloring| B 3 to 3-PreExt| B 3 , that is, we show that if 3-PreExt| B 3 can be solved in polynomial time, then we can solve 3-Fall-Coloring| B 3 by solving a polynomial number of instances of 3-PreExt| B 3 . Let G be a bipartite graph with diameter at most three. Given a cycle C of length 6 and a 3-coloring f of G, we say that C is fall-colored in f if f restricted to C is a fall-coloring. We claim that G has a 3-fall-coloring if and only if there exists a C 6 in G whose 3-fallcoloring can be extended to a proper 3-coloring of G. Observe that, if true, we get the desired reduction since it would suffice to test, for every subset of vertices of size 6 that induce a cycle C, whether a 3-fall-coloring of C can be extended to G (observe that this 3-fall-coloring is unique up to relabeling).

Let (X, Y ) be the bipartition of G. First, suppose that f is a 3-fall-coloring of G. By Lemma 10, we know that f (X) = f (Y ) = {1, 2, 3}. Let v 1 , v 2 , v 3 ∈ X be colored with 1, 2, and 3, respectively. Because G has diameter at most three, we get that N (v i ) ∩ N (v j ) = ∅, for every {i, j} ⊆ {1, 2, 3}, i = j. So, let w i,j ∈ N (v i ) ∩ N (v j ), for each choice of i, j. Since f (v 1 , v 2 , v 3 ) = {1, 2, 3} and f is a proper 3-coloring, we get that {w 1,2 , w 2,3 , w 1,3 } are all distinct, and that f (w i,j ) = where ∈ {1, 2, 3} \ {i, j}. Then the cycle (v 1 , w 1,2 , v 2 , w 2,3 , v 3 , w 1,3 ) is an induced C 6 because G is bipartite and because f is a proper coloring. Conversely, suppose that a 3-fall-coloring f of a cycle C of length 6 can be extended to a proper 3-coloring f of G (note that the fall-coloring of C is unique up to relabeling). A 3-b-coloring is a proper 3-coloring such that each color class has at least one b-vertex. Note that any extension of f is a 3-b-coloring of G, since in C there are already b-vertices of all the 3 colors. Faik [START_REF] Faik | La b-continuité des b-colorations: complexité, propriétés structurelles et algorithmes[END_REF] proved that every 3-b-coloring of a bipartite graph with diameter three is also a 3-fall-coloring1 ; hence, f is a 3-fall-coloring of G. Now, we prove that 3-Fall-Coloring is NP-complete even when restricted to bipartite graphs with diameter at most four. We mention that our proof is an improvement on the proof presented by Laskar and Lyle [START_REF] Laskar | Fall colouring of bipartite graphs and cartesian products of graphs[END_REF], where the constructed graphs have diameter six, although the authors do not mention that in their proof. Proof. We present a reduction from 3-Uniform 2-Col. Consider a 3-uniform hypergraph G on vertices V = {v 1 , . . . , v n } and hyperedges E = {e 1 , . . . , e m }, and let G be constructed as follows (see Figure 9 for an illustration). Add V and E to the set of vertices of G , together with a copy v i of each vertex v i ∈ V ; denote by V the set {v i | v i ∈ V }. Also, add two new vertices v, v , and make v complete to V and v complete to V . Finally, add an edge between e j and each v i ∈ e j for every e j ∈ E, and add the matching {v i v i | i ∈ [n]}. We prove that G is a bipartite graph with diameter four, and that G is a yes-instance of 3-Uniform 2-Col if and only if G is a yes-instance of 3-Fall-Coloring.

First, note that (V ∪ E ∪ {v}, V ∪ {v }) is a bipartition of G . To see that G has diameter four, first note that G -E consists of a perfect matching between V and V , together with a vertex v complete to V and a vertex v complete to V . Observe that this subgraph has diameter three, with the most distant pairs of vertices being v and v , and v i and v j with i = j. Now, consider a hyperedge e ∈ E. Below, we show that the distance between e and any other vertex of G is at most four.

• d(e, v) = 2: let v i ∈ e; then (e, v i , v) is a path in G ;

• d(e, v ) = 3: let v i ∈ e; then (e, v i , v i , v ) is a path in G ; • d(e, v i ) 3 for every v i ∈ V : if v i ∈ e, then (e, v i ) is a path in G . Otherwise, let v j ∈ e; then (e, v j , v, v i ) is a path in G ;

v 1 v 2 • • • v n v 1 v 2 • • • v n e 1 e 2 • • • e m v v V V E V v 1 v 2 • • • v n
• d(e, v i ) 4 for every v i ∈ V : if v i ∈ e, then (e, v i , v i ) is a path in G . Otherwise, let v j ∈ e; then (e, v j , v, v i , v i ) is a path in G ;

• d(e, e ) 4, for every e ∈ E(G) \ e: if there exists v i ∈ e ∩ e , then (e, v i , e ) is a path in G . Otherwise, let v i ∈ e and v j ∈ e , then (e, v i , v, v j , e ) is a path in G . Now, we prove that G is a yes-instance of 3-Uniform 2-Col if and only if G is a yes-instance of 3-Fall-Coloring. First, consider a 2-coloring f of G with no monochromatic hyperedge, and suppose that the used colors are {2, 3}. We extend f to a 3-fall-coloring f of G . For this, color every x ∈ E ∪ {v, v } with 1, and color v i with c ∈ {2, 3} \ f (v i ). One can verify that, because no hyperedge of G is monochromatic in f , the obtained coloring is a fall-coloring of G .

Finally, consider a 3-fall-coloring f of G , and suppose, without loss of generality, that f (v) = 1. This and the fact that v is a b-vertex imply that f (V ) = {2, 3}. Hence, for every e ∈ E(G), since N G (e) ⊆ V and 1 / ∈ f (V ), in order for e to be a b-vertex we must have that f (e) = 1, and that f (N G (e)) = {2, 3}. Therefore, the coloring f restricted to V is a 2-coloring of G with no monochromatic hyperedge.

Proof.

  Consider a complete bipartite graph G = (A ∪ B, E) and a list assignment L such that L(u) ⊆ [k] for every u ∈ V (G). It is easy to see that solving List k-Coloring on G is equivalent to choosing an element c(u) in L(u) for each u ∈ V (G) in such a way that the chosen elements for A have no intersection with the chosen elements of B; more formally, {c(u) | u ∈ A} ∩ {c(u) | u ∈ B} = ∅. Because choosing a color c(u) for u ∈ A actually makes this color available for every v ∈ A and non-available for every v ∈ B, the problem actually consists of choosing which subset of colors S can be used in A, knowing that S = [k] \ S will be the colors available for B. So, we can simply test, for each subset S ⊆ [k], whether S ∩ L(u) = ∅ for every u ∈ A, and S ∩ L(u) = ∅ for every u ∈ B. This takes time O(2 k • k • log k • n) since we need to check the intersection between either S or S and L(u) (which takes time O(k • log k) if we consider the lists are ordered) for every u ∈ V (G).

Theorem 3 .

 3 Let G = (X ∪ Y ) be a bipartite graph, let C ⊆ G be an induced C 6 in G, and let Y C = V (C) ∩ Y . Deciding whether G has a retraction to C is NP-complete, even if Y C dominates X and dist(h, y) 2 for every h ∈ Y C and y ∈ Y .

Figure 4 :

 4 Figure 4: Gadget related to the diagonal h 1 h 4 .

Figure 6 :

 6 Figure 6: Different types of diagonal gadgets.

Figure 7 :

 7 Figure 7: Extension of a retraction of G to H to a retraction of G to H, which is of course also an edge-surjective C 6 -homomorphism of G .

First suppose that a = a u 1 , 3 , 6 .

 136 Because c u 1,3,6 ∈ N (h 1 ), f (h 1 ) = 5, and f (a) = 1, we get that f (c u 1,3,6 ) = 6. And because h 3 ∈ N (b u 1,3,6 ), f (h 3 ) = 3, and f (a) = 1, we get that f (b u 1,3,6 ) = 2. We get a contradiction since {2, 6} ⊆ f (N (u)) and f (u) = 1. Clearly the same argument holds for a = a u 2,3,6 since f (h 5 ) = f (h 1 ) = 5.

Corollary 7 .

 7 Edge-Surjective C 6 -Homomorphism| B 4 is NP-complete. The same holds for Surjective C 6 -Homomorphism| B 4 .

Figure 8 :

 8 Figure 8: Situation where f (h i ) = i for every i ∈ {3, 4, 5, 6}.

Corollary 12 .

 12 Let k, d be positive integers. Then k-Fall-Coloring| B d is polynomial when k 2 or d = 2, and NP-complete when either k 4 and d 3, or k = 3 and d 4.

Theorem 14 . 3 -

 143 Fall-Coloring| B 4 is NP-complete.

Figure 9 :

 9 Figure 9: Graph G related to the hypergraph G = (V, E).

Table 2 :

 2 Row labeled i presents the complexity of the corresponding problems restricted to bipartite graphs with diameter at most i, for every fixed integer k 4.

be obtained from p by giving color k + 1 to both x and y. Now, any extension of p defines an extension of p and vice-versa, since color k + 1 can only appear in the new vertices.

  and v i 3 are emphasized. The image of a vertex is put inside of the node, and its label appears next to it, with the exception of e j . Note that the blank vertices can be colored, from left to right, with p E 1 , p E 3 , p E 1 , and p E 1 . One can see that G has a 3-extension for this precoloring if and only if G has a retraction to C. Also, the fact that {p E 1 , p E 2 , p E 3 } dominates X gives us the property claimed in the statement. It remains to verify that diam(G)

Proof. Given a bipartite graph G = (X ∪ Y, E) and a C 6 , say C, in G with the properties stated in Theorem 3, it suffices to precolor p E i , p V i with i for each i ∈

[START_REF] Bodirsky | The complexity of surjective homomorphism problems -a survey[END_REF]

.

the electronic journal of combinatorics 28(2) (2021), #P2.[START_REF] Hajós | Über eine konstruktion nicht n-färbbarer graphen[END_REF]

Since reference[START_REF] Faik | La b-continuité des b-colorations: complexité, propriétés structurelles et algorithmes[END_REF] is in French, for completeness we present the proof in Appendix A.the electronic journal of combinatorics

[START_REF] Nadimpalli | 3choosable complete bipartite graphs[END_REF](2) (2021), #P2.[START_REF] Hajós | Über eine konstruktion nicht n-färbbarer graphen[END_REF]

* Supported by FUNCAP/CNPq/Brazil Project PRONEM PNE-0112-00061.01.00/16. † Supported by CAPES-PRINT Institutional Internationalization Program, process 88887.468331/2019-00, and French projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), ELIT (ANR-20-CE48-0008), and UTMA (ANR-20-CE92-0027). ‡ Supported by FUNCAP/CNPq/Brazil, Project PRONEM PNE-0112-00061.01.00/16, CNPq Universal 401519/2016-3 and 437841/2018-9, and CNPq Produtividade 304576/2017-4.

Proof. Denote the parts of G by X and Y . It suffices to notice that V 1 , V 2 , V 3 is a 3biclique partition of G if and only if the function f defined as follows is a surjective C 6homomorphism of G B :

and f -1 (6) = Y ∩ V 3 . The theorem thus follows from Corollary 7.

Fleischner et al. [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF] presented a hardness proof for the k-Biclique Partition problem for a general k 3, but since their reduction for values of k larger than 3 can be obtained using the trick presented in Proposition 1, for the sake of simplicity we consider k = 3. Still for the sake of simplicity, we work on the bipartite complement of their construction, which is from the List 3-Coloring problem. So, consider G bipartite with parts X, Y , and a list assignment L such that L(u) ⊆ {1, 2, 3} for every u ∈ V (G). Let G be obtained from G by adding a cycle C = (x 1 , y 2 , x 3 , y 1 , x 2 , y 3 , x 1 ) (which alternatively can be seen as the complete bipartite graph minus the perfect matching

Then, for every u ∈ X, add an edge from u to y i if and only if i / ∈ L(u); do the same for each u ∈ Y and x i . They claim that G has an L-coloring if and only if G has a retraction to C, if and only if G B has a 3-biclique partition. Indeed one can see that any retraction

However, in the reverse implication, it is not necessarily true that a 3-biclique partition V 1 , V 2 , V 3 will map edge x i y i inside of V i for every i ∈ [START_REF] Bodirsky | The complexity of surjective homomorphism problems -a survey[END_REF], as the authors claim. For example, when G is simply an edge uv, and

Nevertheless, their proof does imply that Retract to C 6 is NP-complete. We provided another proof of this fact in Theorem 3 because we needed stronger constraints on G and H in order to prove Corollaries 7 and 9.

k-Fall Coloring

In this section we investigate the complexity of k-Fall Coloring on bipartite graphs with diameter at most d for every pair of integers k, d. As in the case of list coloring problems, again the only case that we leave open is when k = 3 and d = 3. We conjecture that this case is also NP-complete, and we prove in Proposition 13 that, if so, then the cases left open in Table 1 would also be NP-complete. We start with the following technical lemma.

Lemma 10. Let G be a bipartite graph with vertex bipartition (X, Y ) and f be a k-fall-

Proof. Towards a contradiction, suppose that 1 / ∈ f (X), which implies that every v ∈ X has some neighbor in f -1 (1) ⊆ Y ; however, there can be no

2 for every v ∈ X, contradicting the hypothesis that f is a k-fall-coloring.

The following is analogous to Proposition 1.

A 3-b-colorings and 3-fall-colorings

In this section, for the sake of completeness, we present a proof of Faik [START_REF] Faik | La b-continuité des b-colorations: complexité, propriétés structurelles et algorithmes[END_REF].

Theorem 15 (Faik [7]). Let G be a bipartite graph with diameter at most 3. If f is a 3-b-coloring of G, then f is a 3-fall-coloring of G.

Proof. Let (X, Y ) be the bipartition of V (G). By Lemma 10, it holds that that f (X) = f (Y ) = [START_REF] Bodirsky | The complexity of surjective homomorphism problems -a survey[END_REF]. Note that if u, v are within the same part, then N (u)∩N (v) = ∅, as otherwise their distance would be at least four. So, let u ∈ X be of color 1. Because there exists v ∈ X of color 2 and since N (u) ∩ N (v) = ∅, we get that u must have a neighbor of color 3, namely the common neighbor with v. The analogous holds when picking any v ∈ X of color 3; therefore u is a b-vertex. Clearly this argument can be applied to every u ∈ X ∪Y just by renaming the colors and the parts.