List \(3\)-coloring \(C_4\)-free graphs of diameter-\(2\) in polynomial-time
June 29, 2026
Abstract
We show that list \(3\)-coloring a \(C_4\)-free graph of diameter-\(2\) can be done in polynomial-time. Our algorithm is based on a structural characterization showing that many such graphs are not \(3\)-colorable. In particular, we show that \(C_4\)-free graphs of diameter-\(2\) without universal vertices, where the maximum degree is at least \(17\), are not \(3\)-colorable.
1 Introduction↩︎
For an integer \(k\ge 1\), we write \([k] = \{1,2,\ldots, k\}\). Given is a finite simple unweighted connected graph \(G=(V,E)\). A map \(c:V\rightarrow [k]\) for an integer \(k\) is called a \(k\)-coloring if \(c(u)\ne c(v)\) for all edges \(uv\in E\). In such cases, we say that \(G\) is \(k\)-colorable. The smallest \(k\) for which \(G\) admits a \(k\)-coloring is called the chromatic number of \(G\).
\(k\)-Coloring
| Input: | A graph \(G=(V,E)\). |
| Question: | Is \(G\) \(k\)-colorable? |
One can also consider a more general variant called list \(k\)-coloring. Each vertex \(v\) is given a list \(L(v)\subseteq [k]\) of colors it may have; if there exists a \(k\)-coloring \(c:V\rightarrow [k]\) where \(c(v)\in L(v)\), then we say that the graph is list \(k\)-colorable. Note that list \(k\)-colorable graphs are necessarily \(k\)-colorable, but not vice versa.
List \(k\)-Coloring
| Input: | A graph \(G=(V,E)\) and a list \(L:V\rightarrow 2^{[k]}\). |
| Question: | Is \(G\) list \(k\)-colorable? |
2-Coloring is equivalent to showing that a graph is bipartite. \({{\normalfont\mathrm{\small k-Coloring}}}\), and therefore \({{\normalfont\mathrm{\small List k-Coloring}}}\), on the other hand, is NP-complete for all \(k\ge3\) [1]. Since, much attention has been devoted to solving the problems on restricted graphs, such as those with forbidden (induced) subgraphs [2], [3], those on bounded diameter [4], [5], or a combination thereof [6], [7]. There are numerous thorough surveys on the topic [8]–[10]. We study list \(3\)-coloring on bounded diameter.
1.0.0.1 Bounded diameter.
List \(3\)-Coloring Diameter-\(d\)
| Input: | A graph \(G=(V,E)\) of diameter-\(d\) and a list \(L:V\rightarrow 2^{[3]}\). |
| Question: | Is \(G\) list \(3\)-colorable? |
Mertzios and Spirakis showed that \({{\normalfont\mathrm{\small 3-Coloring}}}\) remains NP-complete when the input is restricted to graphs of diameter-\(3\) (and even triangle-free) [4]. In the same paper, they showed that under the Exponential Time Hypothesis, the problem cannot be solved in \(2^{o(\sqrt{n})}\) time; they gave a subexponential-time algorithm to solve \({{\normalfont\mathrm{\small List 3-Coloring Diameter-3}}}\) [4]. This was subsequently improved by Dębski, Piecyk, and Rzążewski to run in \(2^{O((n\log n)^{2/3})}\) time [11] and later by Groenland, Koerts, and Spirkl to \(2^{O(n^{2/3-\epsilon})}\) for any \(\epsilon<1/33\) [12].
For graphs of diameter-\(2\), the computational complexity of both \({{\normalfont\mathrm{\small 3-Coloring}}}\) and \({{\normalfont\mathrm{\small List 3-Coloring}}}\) remains open. Mertzios and Spirakis gave a \(2^{O(\sqrt{n\log n})}\) time algorithm based on dominating sets [4]. The fastest algorithm thus far runs in \(2^{O(n^{1/3}\log^2n)}\) time due to Dębski, Piecyk, and Rzążewski [11].
To better understand the boundary between the intractable (potentially NP-hard) and the tractable (polynomial-time solvable), many have investigated List \(3\)-Coloring Diameter-\(2\) in combination with forbidden subgraphs. One of particular interest is in considering induced \((H_1,H_2,\ldots, H_p)\)-free graphs, which are graphs that do not contain an induced subgraph isomorphic to \(H_i\), for all \(i\in [p]\). A similar notion is an \(H\)-free graph, which does not contain a subgraph isomorphic to \(H\). It has been shown that \({{\normalfont\mathrm{\small List 3-Coloring Diameter-2}}}\) is polynomial-time solvable for
graphs in which centers of induced claws2 form an independent set and quasi-claw-free graphs [13].
induced \(C_s\)-free graphs for \(s=5,6\) [6].
induced \((C_4, C_s)\)-free graphs for \(s\ge 3\) (shown for \(s\in\{3,5,6,7,8,9\}\) in [6], generalized to other \(s\) values in [7].
induced \((C_3,C_7)\)-free graphs [7].
Most of these results follow a similar recipe. Color a subset of the vertices and propagate the color constraints, i.e. for uncolored vertices, remove all colors which appear on their neighbours from the list. Check that the remaining vertices must each have a list of size at most \(2\); as 2-List-Coloring3 can be solved in polynomial-time [14], it remains to show that finding the first suitable pre-coloring takes polynomial-time.
1.0.0.2 Our contribution.
We take a structural approach and show that most \(C_4\)-free graphs of diameter-\(2\) are not \(3\)-colorable.
List \(3\)-Coloring \(C_4\)-free Diameter-\(2\)
| Input: | A \(C_4\)-free graph \(G=(V,E)\) of diameter-\(2\) and a list \(L\). |
| Question: | Is \(G\) list \(3\)-colorable? |
thmLTCDtwfour List \(3\)-Coloring \(C_4\)-free Diameter-\(2\) is polynomial-time solvable.
To show [thm:main], we show that most \(C_4\)-free graphs of diameter-\(2\) are not \(3\)-colorable if the maximum degree is at least \(17\). Determining the maximum degree of a graph can be done in polynomial-time. The list \(3\)-colorability of the remaining finitely many graphs can be hardcoded into a lookup table.
We give a quick overview of the proof. We show that the \(C_4\)-free and diameter-\(2\) conditions impose a rigid structure on the graph. We start by fixing a vertex \(v_0\) of maximum degree \(\Delta\). Letting \(N_i\) denote vertices which are distance-\(i\) away from \(v_0\), assuming \(N_2\ne \emptyset\), we show that vertices in \(N_2\) can be partitioned based on their unique adjacent vertex in \(N_1\). There are \(\Delta\) parts in the partition; we show that each part contains the same number of elements, which is either \(\Delta-2\) or \(\Delta-1\). We also show that every vertex must be of degree \(\Delta-1\) or \(\Delta\), and that between every pair of parts in \(N_2\) which are ‘adjacent’, the vertices therein form a perfect matching. We show that every vertex in \(N_2\) is of one of three types. We then exhaustively check that most graphs containing all possible Types of \(N_2\) vertices are not \(3\)-colorable. This is done by showing that there are too many triangles which forces an unachievable number of vertices of a certain color.
While this is useful in showing a result in the Coloring context, we envision that the improved structural understanding of the class of \(C_4\)-free graphs of diameter-\(2\) can be of use in other related areas.
1.0.0.3 Structure.
In 2, we detail necessary definitions and preliminaries. In 3, we give structural results for \(C_4\)-free graphs of diameter-\(2\). In 4, we prove necessary conditions for a proper \(3\)-coloring to exist for \(C_4\)-free graphs of diameter-\(2\). In 5, we show that most graphs in the class are not \(3\)-colorable. In 6, we prove [thm:main]. We give concluding remarks in 7.
2 Preliminaries↩︎
Let \(G=(V,E)\) be a graph. Let \(u,v\in V\). We say that \(u\) covers \(v\) via adjacency if \(uv\in E\). We say that a vertex \(u\) covers \(v\) via a proxy \(w\) (or just covers \(v\) via proxy if the context is clear) if there exists a vertex \(w\) such that \(uw,wv\in E\). The degree of \(u\), denoted \(\deg_G(u)\), is the number of edges incident with \(u\). We remove the subscript and write \(\deg(u)\) if the reference graph is clear. The minimum degree of \(G\) is \(\delta(G) = \min_{v} \deg(v)\); the maximum degree of \(G\) is \(\Delta(G) = \max_{v}\deg(v)\).
We consider unweighted graphs. The length of a path is the number of edges it contains. The distance between two vertices is the number of edges in a shortest path between them. The diameter of \(G\), written \(\mathop{\mathrm{diam}}(G)\) is the maximum distance between any pair of its vertices. Note that in a graph of diameter-\(2\), \(u\) covers \(v\) via adjacency or via proxy, or both.
We write \(N^G_i(v) = \{u: d(u,v) = i\}\) to denote the set of vertices which are distance \(i\) away from \(v\). We drop the superscript if there is no ambiguity in the reference graph. Let \(u,v\in V\). We merge \(u\) and \(v\) by replacing them with a new vertex \(w\), where \(N_1(w) = N_1(u)\cup N_1(v)\).
Let \(S\subseteq V\). The induced subgraph \(G[S]\) is the graph whose vertex set is \(S\) and whose edge set consists of all elements in \(E\) with both endpoints in \(S\). We say that \(G\) is induced \((H_1, H_2,\ldots, H_p)\)-free if \(G\) does not contain an induced subgraph isomorphic to \(H_i\) for all \(i\in[p]\). We say that \(G\) is \(H\)-free if \(G\) does not contain a subgraph that is isomorphic to \(H\).
In this paper, we consider \(C_4\)-free graphs. These are induced \((C_4,D_4,K_4)\)-free graphs, where \(K_4\) is the complete graph on \(4\) vertices and \(D_4\) is a diamond graph, a graph on four vertices and five edges (so a \(K_4\) without an edge). Since graphs containing \(K_4\) as a subgraph are not \(3\)-colorable, and since identifying a \(K_4\) takes polynomial-time, one can also restrict to induced \((C_4,D_4)\)-graphs. Nevertheless, for ease of notation, we formulate our results for \(C_4\)-free graphs. Note that there is a so-called diamond elimination rule [4]. It is not immediately clear if this rule preserves induced \(C_4\)-freeness. Thus, we have decided to also exclude \(D_4\) as an induced subgraph. See 7 for a discussion on the matter.
The following lemma is in the spirit of Observation 1 in [4].
Lemma 1. Let \(G=(V,E)\) be a \(C_4\)-free graph. If \(G\) has more than two vertices, then for every \(u\in V\), the maximum degree of \(G[N_1(u)]\) is \(1\).
Proof. If there was a vertex \(y\) in \(G[N_1(u)]\) of degree-\(2\) with neighbours \(x\) and \(z\), then \(uxyz\) is a \(C_4\), which is prohibited. ◻
3 Characterizing \(C_4\)-free graphs of diameter-\(2\)↩︎
We introduce notation which will be used in the rest of this paper. We write \(G=(V,E)\) to mean a \(C_4\)-free graph of diameter-\(2\). We let \(\Delta\) denote the maximum degree of \(G\), and let \(v_0\) be a vertex with degree \(\Delta\). We call \(v_0\) a root. If \(\Delta=2\), then \(G\) must be isomorphic to \(C_5\), which is \(3\)-colorable. We assume \(\Delta\ge 3\). Let \(N_1 = N_1(v) = \{x_1,x_2,\ldots, x_\Delta\}\) be the set of neighbours of \(v_0\), and let \(N_2 = N_2(v)\).
A vertex that is adjacent to every other vertex is called a universal vertex. List \(3\)-Coloring \(C_4\)-free Diameter-\(2\) is polynomial-time solvable if there exists a universal vertex.
Lemma 2. If \(N_2=\emptyset\), then List \(3\)-Coloring \(C_4\)-free Diameter-\(2\) is polynomial-time solvable.
Proof. If there exists a proper list \(3\)-coloring, there exists one where \(v_0\) is given one of at most three colors in \(L(v_0)\). Each guess returns an instance of list-\(2\) coloring, which can be solved in polynomial-time [14]. ◻
So we assume henceforth that \(N_2\) is non-empty. See 1 for all \(C_4\)-free graphs of diameter-\(2\) when \(\Delta\le 3\).
3.1 Overview of results↩︎
We give an overview of results in 3. By taking a vertex \(v_0\) with \(\deg(v_0) = \Delta\) as root, we show that \(N_2= N_2(v_0)\) has a canonical partition \(N_2 = \bigcup_{i=1}^\Delta V_i,\) where \(V_i\cap V_j = \emptyset\) for all \(i\ne j\), \(|V_1| = |V_2| = \cdots = |V_\Delta|\) (7), and \(|V_i|\in \{\Delta-2,\Delta -1\}\) (8). Every vertex in \(N_2\) is of Types-\(1\), \(2\), or \(3\) (see 3.3), and these vertices are of degrees \(\Delta,\Delta-1\), and \(\Delta\), respectively ([lem:T1Delta,lem:T2Delta-1,lem:T3Delta]). If \(N_2\) contains a Type-\(2\) or a Type-\(3\) vertex, then \(|V_i| = \Delta-2\); if \(|V_i| = \Delta-1\), then \(N_2\) contains only Type-\(1\) vertices (9). If \(N_2\) contains a Type-\(2\) vertex, then a different rooting gives a canonical partition that contains a Type-\(1\) vertex (14). This reduces the number of cases we need to consider in 5. Lastly, there can only be \(C_3\)’s in \(G[N_2]\) between two adjacent vertices which are both not Type-\(2\) (15). In general, this means there are usually a lot of \(C_3's\) in \(G[N_2]\). We use this fact to show non-\(3\)-colorability results in [sec:Color,sec:ColorTypes].
3.2 A canonical partition of \(N_2\)↩︎
Lemma 3. Every vertex in \(N_2\) has exactly one neighbour in \(N_1\).
Proof. Let \(u\in N_2\). The vertex \(u\) must cover \(v_0\) via proxy, so it must have at least one neighbour in \(N_1\). If there are two such neighbours, say \(x_i,x_j\in N_1\), then \(v_0x_iux_j\) forms a \(C_4\). ◻
Lemma 4. Every vertex in \(N_1\) has at least one neighbour in \(N_2\).
Proof. Let \(x\in N_1\). We wish to show that \(x\) has a neighbour in \(N_2\). Let \(u\in N_2\). By 3, \(uy\in E\) where \(y\in N_1\). If \(xy\notin E\), then \(u\) must cover \(x\) via a proxy \(w\in N_2\), i.e., \(uw,wx\in E\). So \(x\) has a neighbour in \(N_2\).
So suppose \(xy\in E\). Since \(\Delta\ge 3\), \(v_0\) has a neighbour \(z\) that is not \(x\) nor \(y\). By 1, \(G[N_1]\) does not contain a \(P_3\), and so \(zx,zy\notin E\). Then \(u\) must cover \(z\) via a proxy \(v\in N_2\), and \(v\) must cover \(x\) via a proxy \(w\in N_2\). So \(x\) has a neighbour in \(N_2\). ◻
By 3, every vertex in \(N_2\) is adjacent to exactly one vertex in \(N_1\). We partition the vertex set \(N_2\) based on this adjacency; in particular, let \(V_i\) denote the set of vertices in \(N_2\) which are adjacent to \(x_i\), for \(i\in[\Delta]\). Note that \(|V_i|\ge 1\) for all \(i\), by 4. We call such a partition \(V_1, V_2,\ldots, V_\Delta\) a canonical partition (with respect to \(v_0\)) of \(N_2\). See 3 for an example.
We say that two parts \(V_i, V_j\) are adjacent if a vertex of \(V_i\) has a neighbour in \(V_j\).
Lemma 5. Suppose \(x_i\) and \(x_j\) are non-adjacent. Then \(V_i\) and \(V_j\) are adjacent, and the edges between \(V_i\) and \(V_j\) form a perfect matching. In particular, \(|V_i|=|V_j|\).
Proof. As \(x_ix_j\notin E\), every vertex in \(V_i\) must cover \(x_j\) via a proxy in \(V_j\). Similarly, every vertex in \(V_j\) must cover \(x_i\) via a proxy in \(V_i\). Two vertices in \(V_i\) cannot have a common neighbour apart from \(x_i\), as that would result in a \(C_4\). So \(|V_i|\le |V_j|\). Similarly, \(|V_j|\le |V_i|\). We obtain our perfect matching and the claim follows. ◻
Note also that if \(V_i\) and \(V_j\) are non-adjacent, then \(x_i\) and \(x_j\) must be adjacent.
Lemma 6. \(V_i\) is adjacent to at least \(\Delta-2\) parts for all \(i\in [\Delta]\).
Proof. By 1, \(x_i\) has at most one neighbour in \(N_1\), and so \(x_i\) is non-adjacent to at least \(\Delta-2\) vertices in \(N_1\). By 5, \(V_i\) is adjacent to at least \(\Delta-2\) parts. ◻
Lemma 7. The canonical partition is balanced, i.e., \(|V_1|=|V_2|=\cdots = |V_\Delta|\).
Proof. Let \(x_i\in N_1\). If \(x_i\) is not adjacent to any vertices in \(N_1\), then we are done by 5. So suppose \(x_ix_j\in E\) for some \(x_j\in N_1\). By 1, \(x_i\) and \(x_j\) have no other neighbours in \(N_1\). By invoking 5 twice, we obtain \(|V_i|=|V_k|=|V_j|\) for each \(k\in [\Delta]\setminus\{i,j\}\). Such a set \([\Delta]\setminus\{i,j\}\) is non-empty as \(\Delta\ge 3\), which gives the required result. ◻
Lemma 8. \(|V_i|\in\{\Delta-2, \Delta-1\}\) for all \(i \in [\Delta]\).
Proof. For the upper bound, observe that \(\Delta \ge\deg(x_i)\ge |V_i|+1\), where the \(+1\) term comes from the edge \(x_iv_0\). We now show the lower bound (see 2 for an illustration). If there are two non-adjacent parts, select these as \(V_i\) and \(V_j\). Otherwise, select any pair of parts. Let \(v\in V_i\). We study how vertices in \(V_j\) are covered by \(v\) via proxies. By 5 and 6, \(v\) is adjacent to a vertex in every part that is not \(V_j\), so \(v\) is adjacent to a vertex in at least \(\Delta-2\) parts. If \(|V_j|\le \Delta-3\), then by the pigeonhole principle, two neighbours of \(v\) must have the same neighbour in \(V_j\). This gives a \(C_4\), and thus \(|V_j|\ge \Delta-2\). By 7, \(|V_i|=|V_j|\ge \Delta-2\) for all \(i\in [\Delta]\). ◻
![Figure 2: A visualization of the lower bound |V_i|\ge\Delta-2 in the proof of 8, for the case when there are non-adjacent parts. The figure shows a subgraph of G[N_2], illustrating how u\in V_i covers the vertices of a non-adjacent part V_j. The dotted line between V_i and V_j indicate the non-adjacency. The additional vertices in V_1,\ldots, V_{j-1},V_{j+1}, V_\Delta are omitted for clarity.](/article/2606.30282/_pdflatex/godmvfrj.png "fig:")
Lemma 9. If there are non-adjacent parts, then \(|V_i|=\Delta-2\) for all \(i\in [\Delta]\).
Proof. Let \(V_i,V_j\) be non-adjacent parts. Let \(u_i\in V_i\). Then \(u_i\) covers the vertices of \(V_j\) only via proxy in other parts; there are \(\Delta-2\) such edges, and thus \(|V_j|\le \Delta-2\). Consequently, by [lem:V_iUniformSize,lem:V_iSizeLowerBound], we obtain \(|V_i| = \Delta-2\) for all \(i\in [\Delta]\). ◻
Note that if \(|V_i| = \Delta-1\), then all parts are pairwise adjacent, i.e., \(N_1\) forms an independent set.
3.3 Classifying vertices in \(N_2\)↩︎
Let \(i\in [\Delta]\) and let \(v\in V_i\). We say that \(v\) is of
Type-\(1\) if \(x_i\) has no neighbours in \(N_1\) and \(v\) has no neighbours in \(V_i\);
Type-\(2\) if \(x_i\) has a neighbour in \(N_1\) and \(v\) has no neighbours in \(V_i\);
Type-\(3\) if \(x_i\) has a neighbour in \(N_1\) and \(v\) has one neighbour in \(V_i\);
Lemma 10. Every vertex in \(N_2\) is of Type-\(1\), of Type-\(2\), or of Type-\(3\).
Proof. Since \(N_1\) is \(P_3\)-free by 1, \(x_i\) has at most one neighbour in \(N_1\). Suppose first that \(x_i\) has a neighbour in \(N_1\). Let \(v\in V_i\). Since \(V_i\subseteq N_1(x_i)\), \(v\) has at most one neighbour in \(V_i\) by 1. Then \(v\) is either of Type-\(2\) or of Type-\(3\).
So suppose \(x_i\) has no neighbours in \(N_1\), and suppose \(v\) has a neighbour \(y\) in \(V_i\). Note that \(v\) must cover \(x_j\) via proxy in \(V_j\), for all \(j\in[\Delta]\setminus\{i\}\). This gives \(\deg(v)\ge\Delta-1 + 2 = \Delta+1\), where the \(+2\) term comes from the edges \(vy, vx_i\). This contradicts our choice of \(\Delta\), and so \(v\) cannot have a neighbour in \(V_i\). Thus \(v\) must be of Type-\(1\). ◻
![Figure 3: A C_4-free G of diameter-2 with maximum degree 4. (a) G without the edges in E(G[N_2]). c_1,c_2,d_1,d_2 are Type-1 vertices, b_1,b_2 are Type-2 vertices, and a_1,a_2 are Type-3 vertices. (b) G[N_2]. The dotted line between V_1 and V_2 indicates that the two parts are non-adjacent. In accordance with 15, b_1,b_2 are not contained in a C_3. a_1,c_2,d_2 forms a C_3 as they are pairwise adjacent and none of the vertices are Type-2.](/article/2606.30282/_pdflatex/fdwhrktj.png "fig:")
We refer the reader to 3 to see an example of a \(C_4\)-free graph of diameter-\(2\) with \(\Delta=4\). We show the degree of Type-\(i\) vertices for \(i\in[3]\).
Lemma 11. A vertex of Type-\(1\) is of degree \(\Delta\).
Proof. Let \(v\in V_i\) be of Type-\(1\). Then \(v\) must cover all vertices in \(N_1\) via adjacency or via proxy. Via adjacency, it can cover exactly one vertex \(x_i\), since by assumption, \(x_i\) has no neighbours in \(N_1\). All other \(\Delta-1\) vertices in \(N_1\) must be covered via proxy, and no two vertices in \(N_1\) can be covered by the same proxy, by 3. So \(\deg(v) = \Delta\). ◻
Lemma 12. A vertex of Type-\(2\) is of degree \(\Delta-1\).
Proof. Let \(v\in V_i\) be of Type-\(2\). Then \(v\) must cover all vertices in \(N_1\) via adjacency or via proxy. Via adjacency, it can cover exactly one vertex \(x_i\); using \(x_i\) as proxy, it also covers another vertex \(x_j\). All other \(\Delta-2\) vertices in \(N_1\) must be covered via proxy, and no two vertices in \(N_1\) can be covered by the same proxy, by 3. It cannot cover vertices in \(N_1\) twice via proxy, as that would form a \(C_4\). So \(\deg(v) = \Delta-1\). ◻
Lemma 13. A vertex of Type-\(3\) is of degree \(\Delta\).
Proof. This case is similar to the proof of 12. It requires the \(\Delta-1\) edges as described in the proof, and it has an additional edge to a neighbour in the same part. So the degree of the vertex must be \(\Delta\). ◻
So every vertex in \(N_2\) is of degree \(\Delta-1\) or \(\Delta\). By definition, each part \(V_i\) can contain vertices of only Type-1, only Type-2, only Type-3, or only Type-2 and Type-3. In the first three cases, we say that \(V_i\) is a part of Type-\(j\), for \(j\in[3]\).
The following lemma states that if \(N_2\) contains a Type-\(2\) vertex, then we may assume that the canonical partition has a Type-\(1\) part. This will be helpful in 5 to reduce the number of cases.
Lemma 14. If \(N_2\) contains a vertex of Type-\(1\) or Type-\(2\), then there exists a vertex \(w_0\) such that the canonical partition with \(w_0\) as root contains a Type-\(1\) part.
Proof. We show an equivalent statement, that there exists a part which is adjacent to all other parts. Let \(v\in V_i\). If \(v\) is of Type-\(1\), then \(V_i\) is adjacent to all other parts by definition and we are done. So suppose \(v\) is of Type-\(2\). By definition, \(x_i\) has a neighbour \(x_j\) in \(N_1\). So \(\deg(x_i) = |V_i| + 2\), where the \(+2\) term comes from the edges \(x_iv_0\) and \(x_ix_j\). As \(|V_i|= \Delta-2\) by 9, we have \(\deg(x_i)=\Delta\). Take \(x_i\) as the root (instead of \(v_0\)). Then \(v\in N_1(x_i)\), and \(v\) has no neighbours in \(N_1(x_i)\). In the corresponding canonical partition, the part corresponding to \(v\) must be adjacent to all other parts, since \(v\) has no neighbours in \(V_i\). This gives the required statement. ◻
3.4 Triangles in \(N_2\)↩︎
The following lemma states that there are in general a lot of \(C_3\)’s in \(G[N_2]\). These appear only between adjacent vertices which are not Type-\(2\). See [fig:graph95II].
Lemma 15. Suppose \(|V_i| = \Delta-2\) for all \(i\in [\Delta]\). Let \(u,v\in N_2\) be adjacent vertices in different parts. Then \(uv\) is in a \(C_3\) in \(G[N_2]\) if and only if \(u\) and \(v\) are both not Type-\(2\).
Proof. Let \(u\in V_i, v\in V_j\) such that \(uv\in E\). Let \(u,v\) be of Type-\(a\) and Type-\(b\), respectively, for \(a,b\in [3]\). We write \((a,b)\) to consider the \(9\) possible cases (this reduces to \(6\) by symmetry). If \(b\in\{2,3\}\), then let \(V_k\) denote the part which is non-adjacent to \(V_j\). If \(b=3\), then let \(w\in V_j\) denote the neighbour of \(v\) in \(V_j\).
For the remainder of this proof, we write \(p(u)\) to denote the number of vertices in \(V_j\) which are covered by \(u\) via proxy. As \(|V_j|=\Delta-2\) by assumption and as \(u\) must cover all vertices of \(V_j\), we must have \(p(u)\in \{\Delta-3, \Delta-2\}\). Indeed, \(p(u)>\Delta-2\) will lead to a vertex being covered twice via proxy and hence a \(C_4\); on the other hand, \(p(u) < \Delta-3\) will mean that \(u\) does not cover all vertices of \(V_j\), violating the diameter-\(2\) condition. If \(p(u) = \Delta-3\), then \(u\) covers each vertex of \(V_j\) exactly once. If \(p(u) = \Delta-2\), then one vertex must be covered twice, since \(v\) is covered via adjacency. To prevent covering the same vertex twice via proxy, this would mean \(v\) must be covered once via adjacency and once via proxy. Then, \(u\) and \(v\) must lie in a \(C_3\).
It remains to show that \(p(u) = \Delta-2\) if and only if \((a,b)\in \{(1,1),(1,3),(3,3)\}\).
3.4.0.1 Case 1: \((a,b)=(1,1)\).
By 11, since we do not consider the edge \(x_iu\) in \(G[N_2]\), we have \(\deg_{G[N_2]}(u) = \Delta-1\). The edge \(uv\) does not cover any vertices of \(V_j\) via proxy. Each of the remaining \(\Delta-2\) edges will cover one vertex in \(V_j\) via proxy, since \(V_i\) and \(V_j\) are adjacent to all parts. So \(p(u) = \Delta-2\).
3.4.0.2 Case 2: \((a,b)\) is \((1,2)\) (or \((2,1)\)).
By 11, \(\deg_{G[N_2]}(u) = \Delta-1\). Again, \(uv\) does not contribute to \(p(u)\) just like in Case 1. Of the remaining \(\Delta-2\) edges, one is lost (i.e. it does not cover anything in \(V_j\) via proxy) as \(V_k\) is adjacent to \(V_i\) and is non-adjacent to \(V_j\). Thus \(p(u) = \Delta-3\). In case of \((2,1)\), we swap the roles of \(u\) and \(v\).
3.4.0.3 Case 3: \((a,b)\) is \((1,3)\) (or \((3,1)\)).
By 11, \(\deg_{G[N_2]}(u) = \Delta-1\). Via \(uv\), we also cover \(w\) via proxy. Of the remaining \(\Delta-2\) edges, one is lost as \(V_k\) is non-adjacent to \(V_j\). Thus, \(p(u) = 1 + \Delta-3 = \Delta-2\).
3.4.0.4 Case 4: \((a,b) = (2,2)\).
By 12, \(\deg(u)_{G[N_2]} = \Delta-2\). The edge \(uv\) does not contribute to \(p(u)\). From the remaining \(\Delta-3\) edges, we get that \(p(u)\le \Delta-3\). However, we lose one edge as \(V_k\) is non-adjacent to \(V_j\). Thus, \(p(u) < \Delta-3\) which means this case is impossible.
3.4.0.5 Case 5: \((a,b)\) is \((2,3)\) (or \((3,2)\)).
By 12, \(\deg_{G[N_2]}(u) = \Delta-2\). Via \(uv\), we also cover \(w\) via proxy. Of the remaining \(\Delta-3\) edges, one is again lost to \(V_k\), and thus \(p(u) = 1 + \Delta-4 = \Delta -3\). (Compared to Case 4, \(u\) now also covers a vertex \(w\) of \(V_j\) via proxy using the edge \(uv\).)
3.4.0.6 Case 6: \((a,b) = (3,3)\).
By 13, \(\deg_{G[N_2]}(u) = \Delta-1\). Via \(uv\), we also cover \(w\) via proxy. Of the remaining \(\Delta-2\) edges, one is lost to \(V_k\), and thus \(p(u) = 1 + \Delta-3 = \Delta-2\). ◻
Note that if vertices \(u,v\) are adjacent and are in the same parts, then \(uv\) cannot be in a \(C_3\) in \(G[N_2]\). If it was, then \(u,v\) must have a common neighbour in another part, which results in a \(C_4\). The next corollary follows immediately from Case \(4\) in the proof of 15.
Corollary 16. Two Type-\(2\) vertices cannot be adjacent.
4 Necessary conditions for a proper \(3\)-coloring↩︎
Throughout this section, we assume the existence of a proper 3-coloring \(c:V\rightarrow [3]\) and show some necessary conditions regarding the canonical partition and \(\Delta\). Without loss of generality, we assume \(c(v_0) = 1\). Then \(c(x_i)\in \{2,3\}\) for all \(i\), and so the vertices in \(V_i\) may only receive colors from \([3]\setminus \{c(x_i)\} = \{1,5-c(x_i)\}\). We say that \(V_i\) is of color class \(5-c(x_i)\), denoted by \(c(V_i) = 5 - c(x_i)\). For example, if \(c(x_i) = 2\), then \(V_i\) is of color class \(3\) or \(c(V_i) = 3\). If \(c(x_i) = 3\), then \(V_i\) is of color class \(2\) or \(c(V_i)=2\).
Lemma 17. Suppose \(V_i\) and \(V_j\) are non-adjacent parts. If there exists a proper \(3\)-coloring, then they must be of different color classes, i.e., \(c(V_i)\ne c(V_j)\).
Proof. As \(x_i\) and \(x_j\) are adjacent, \(c(x_i)\ne c(x_j)\). So \(c(V_i)\ne c(V_j)\). ◻
Suppose \(c(V_1) = c(V_2) = 2\). By the contrapositive of 17, \(V_1,V_2\) are adjacent. Suppose also that both parts contain a non-Type-2 vertex \(u_1\in V_1, u_2\in V_2\) where \(u_1u_2\in E\). By 15, \(u_1\) and \(u_2\) lie in a \(C_3\). Since \(c(V_1) = c(V_2)\), the third point of the \(C_3\), say \(u_3\), must be in a part of color class \(3\). We say that \(u_1u_2u_3\) is a \((V_1,2)\)-triangle. Formally, we call a \(C_3\) \(xyz\) a \((V_i,2)\)-triangle if \(x\in V_i\) where \(c(V_i) = 2\), \(y\in V_j\) where \(c(V_j) = 2\) and \(V_i\ne V_j\), and \(z\in V_k\) where \(c(V_k) = 3\). In other words, a \((V_i,2)\)-triangle contains a vertex from \(V_i\), a vertex from the same color class as \(V_i\), and a vertex from a different color class from \(V_i\).
For example, consider [fig:graph95II]. Suppose \(c(V_1) = c(V_3) = 2\) and \(c(V_2)=c(V_4) = 3\) (it is routine to check that this would not be extendable to a proper \(3\)-coloring). Then \(a_1c_2d_2\) and \(a_2c_1d_1\) are two \((V_1,2)\)-triangles. It is worth noting that they are also both \((V_3,2)\)-triangles.
Lemma 18. Suppose \(V_1\) contains a Type-\(1\) vertex or a Type-\(3\) vertex, and suppose \(c(V_1) = 2\). Consider two \((V_1,2)\)-triangles \(abc, xyz\) where \(a,x\in V_1\). The \(C_3\)’s must be vertex disjoint except possibly at the vertex in \(V_1\), i.e., \(\{b,c\}\cap\{y,z\}=\emptyset\).
Proof. Otherwise, we need to consider two cases. Assume without loss of generality that \(b=y\) if \(\{b,c\}\cap\{y,z\}\ne\emptyset\). The two cases are \(a\ne x, b=y\) and \(a=x,b=y\). In the first case, \(b\) has two neighbours \(a,x\) in \(V_1\), which means \(x_1 a b x\) forms a \(C_4\). In the second case, \(c,z\) are both neighbours of \(a\) and \(b\). So \(azbc\) forms a \(C_4\). In both cases we obtain a \(C_4\), which gives the required contradiction. ◻
18 ensures that vertices of color \(3\) in \((V_1,2)\)-triangles are distinct.
Lemma 19. Suppose \(c(V_1) = 2\). Suppose there at least \(t\)-many \((V_1,2)\)-triangles. Let \(d\) denote the number of parts of color class \(3\). Then there exists a part of color class \(3\), which contains at least \(t/d\) vertices which must be given the color \(3\).
Proof. This follows immediately from 18, as vertices with color \(3\) in \((V_1,2)\)-triangles must be distinct. ◻
Lemma 20. Suppose there are at least \(3\) parts \(V_i,V_j,V_k\) of the same color class. If there exists a proper \(3\)-coloring, then each part must contain the same even number \(\ell\) of vertices, and in each of \(V_i,V_j,V_k\), exactly \(\ell/2\) vertices must be colored \(1\) and exactly \(\ell/2\) vertices must be colored \(c(V_i)\).
Proof. By the contrapositive of 17, \(V_i,V_j,V_k\) are pairwise adjacent. By 5, there is a perfect matching on the vertices in any pair of parts \(V_i,V_j,V_k\). Suppose without loss of generality that \(c(V_i) = 2\). Suppose \(\alpha\) vertices of \(V_i\) are colored \(1\) and \(\ell - \alpha\) vertices are colored \(2\). Then \(\ell - \alpha\) vertices of \(V_j\) are colored \(1\) and \(\alpha\) are colored \(2\) (by the matching on \(V_i\) and \(V_j\)), and similarly \(\ell - \alpha\) vertices of \(V_k\) are colored \(1\) and \(\alpha\) are colored \(2\) (by the matching on \(V_i\) and \(V_k\)). By comparing the perfect matching on \(V_j\) and \(V_k\), we must have that \(\ell - \alpha\) vertices of \(V_k\) are colored \(2\). This means that \(\ell - \alpha = \alpha\), which gives \(\alpha = \ell/2\). ◻
Corollary 21. Suppose \(\Delta\ge4\). If \(|V_i|=\Delta-2\) and if \(\Delta\) is odd, \(G\) is not \(3\)-colorable.
Proof. Suppose there is a proper \(3\)-coloring. If \(\Delta\ge 5\), then there are at least three parts of the same color class. If \(|V_i|= \Delta-2\), then \(\Delta\) must be even by 20. ◻
5 Conditioning on vertices of certain Types↩︎
In this section, we exhaustively check the list 3-colorability of all possible graph configurations for \(\Delta\ge 17\). We do this by considering when \(N_2\) contains only Type-\(1\) vertices (23 and 27), only Type-\(3\) vertices (26), only Type-\(1\) and Type-\(2\) vertices (24), only Type-\(1\) and Type-\(3\) vertices (25), and vertices of all three types (28). We consider the cases based on proof similarity. For all cases apart from 28, we show that the claims hold for \(\Delta\ge 4\).
We begin with the following lemma, which will be used in the proofs of [lem:T1Delta-2,lem:ColorT1andT2,lem:ColorT1T3].
Lemma 22. Suppose \(\Delta\ge 4\), and let \(v\in N_2\) be a Type-\(1\) vertex. Then the number of edges incident to \(v\) which are contained in a \(C_3\) is even.
Proof. If the number in the claim is odd, then at least two of the \(C_3\)’s must share an edge, which would result in a \(C_4\). This is a contradiction. ◻
Lemma 23. Suppose \(\Delta\ge 4\). Suppose \(N_2\) contains vertices only of Type-\(1\), and suppose \(|V_1| = \Delta-2\). If such a graph exists, then it is not \(3\)-colorable.
Proof. If \(\Delta\) is odd, then by 21, the graph would not be \(3\)-colorable. So we assume \(\Delta\) is even. Let \(v\in V_1\). By 15, all incident edges of \(v\) in \(G[N_2]\) is in a \(C_3\). But there are exactly \(\deg_{G[N_2]}(v) = \Delta-1\) many such edges, which is an odd number of edges. This contradicts 22, and thus such graphs do not exist. ◻
Lemma 24. Suppose \(\Delta\ge 4\). Suppose \(N_2\) contains vertices only of Type-\(1\) and Type-\(2\), and it contains at least one vertex of each type. If such a graph exists, then it is not \(3\)-colorable.
Proof. By 9, each part contains \(\Delta-2\) elements. By 21, the graph is not \(3\)-colorable when \(\Delta\) is odd. So we assume \(\Delta\) is even. By 16, there are \(\Delta-2\) Type-\(1\) parts and \(2\) Type-\(2\) parts. Relabelling as needed, let \(V_1\) be a Type-\(1\) part, and let \(v\in V_1\). Observe that in \(G[N_2]\), exactly \(\Delta-3\) edges incident to \(v\) are contained in a \(C_3\), by [lem:T1Delta,lem:TypeTriangles]. Since \(\Delta\) is even, this number is odd. This contradicts 22, and thus such graphs do not exist. ◻
The proof of the following lemma follows a similar argument used in the proof of 23, and is therefore omitted.
Lemma 25. Suppose \(\Delta\ge 4\). Suppose \(N_2\) contains vertices only of Type-\(1\) and Type-\(3\), and it contains at least one vertex of each type. If such a graph \(G\) exists, then it is not \(3\)-colorable.
Lemma 26. Suppose \(\Delta\ge 4\). Suppose \(N_2\) contains vertices only of Type-\(3\). Then \(G\) is not \(3\)-colorable.
Proof. By 9, \(|V_i| = \Delta-2\). By 21, \(\Delta\) is even. Relabelling as needed, let \(V_i,V_{i+1}\) for \(i=1,3,\ldots, \Delta-1\) be the non-adjacent pairs. This means that \(v_0x_ix_{i+1}\) forms a \(C_3\) for every \(i=1,3,\ldots, \Delta-1\). Non-adjacent parts belong to different color classes by 17. By relabelling as needed, we assume \[c(V_i) = \begin{cases} 2, \quad \text{if i is even}\\ 3, \quad \text{if i is odd}\\ \end{cases}\] Because the vertices in \(V_i\) form a perfect matching by definition of Type-\(3\) vertices, half the vertices in \(V_i\) must be colored with \(1\) and the other half with \(c(V_i)\).
By 15 Case 6, all edges in \(G[N_2]\) are contained in a \(C_3\). There are exactly \((\Delta/2 - 1)(\Delta-2)\) many \((V_2,2)\)-triangles, each of which contains a unique vertex of color \(3\). As \(V_1\) and \(V_2\) are non-adjacent, there are \(\Delta/2 - 1\) parts of color class \(3\) which could contain such vertices. Then by 19, there must be at least one part of color class \(3\), say \(V_j\), which has at least \((\Delta/2 - 1)(\Delta-2) / (\Delta/2 - 1) = \Delta-2\) vertices with color \(3\). So all vertices of \(V_j\) must be of color \(3\). But this is not possible, since the vertices in \(V_j\) form a perfect matching. ◻
For the penultimate case, we need the definition of a Moore graph. All \(r\)-regular graphs (every vertex is of the same degree \(d\)) of diameter-\(d\), have at most \(1+d\sum_{i=0}^{r-1} (d-1)^i\) vertices. An \(r\)-regular graph of diameter-\(d\) that has exactly this many vertices is called a Moore graph. Specifically for our case \(d=2\), a regular graph of diameter-\(2\) and girth 5 is a Moore graph. The degree of a diameter-\(2\) Moore graph is known to be \(2,3,7,\) or \(57\) [15]. For \(2,3,7\), the corresponding diameter-\(2\) Moore graphs are unique, and they are the cycle graph on \(5\) vertices, the Petersen graph, and the Hoffman-Singleton graph, respectively. The existence of a diameter-\(2\) Moore graph with degree-\(57\) is still not known.
Lemma 27. Suppose \(\Delta\ge 4\). Suppose \(N_2\) contains vertices only of Type-\(1\), and suppose \(|V_1| = \Delta-1\). Then \(G\) must be isomorphic to a Moore graph, and List \(3\)-Coloring \(C_4\)-free Diameter-\(2\) can be solved in constant time for such inputs.
Proof. We show first that the graph \(G\) must be \(C_3\)-free. Within \(G[N_2]\), each vertex is of degree \(\Delta-1\) by 11. This implies that no vertex can cover another vertex in another part twice, as otherwise it would fail to cover all vertices in the part. So \(G[N_2]\) must be \(C_3\)-free. Observe that \(v_0\) and the vertices in \(N_1\) cannot be in a \(C_3\), since no two vertices of \(N_1\) nor two vertices in \(V_i\) are adjacent. It follows that \(G\) must be \(C_3\)-free, and thus \(G\) must be \(C_3\)-free and \(C_4\)-free.
Observe that \(G\) must be regular. Indeed, all vertices in \(N_1\) is of degree \(\Delta\) since each part has \(\Delta-1\) elements. Furthermore, all vertices in \(N_2\) are Type-\(1\) by 9, and thus of degree \(\Delta\) by 11.
So \(G\) is a regular graph of diameter-\(2\) and girth \(5\), and thus \(G\) must be isomorphic to a Moore graph. Since there are only finitely many Moore graphs, this instance of List \(3\)-Coloring \(C_4\)-free Diameter-\(2\) can be solved in constant time. ◻
For the final lemma, we require a stronger condition on the max degree \(\Delta\).
Lemma 28. Suppose \(\Delta\ge 17\). Suppose \(N_2\) contains vertices of all three types. Then \(G\) is not \(3\)-colorable.
Proof. By 9, \(|V_i| = \Delta-2\). By 21, \(\Delta\) is even. Let \(V_i\) be a part with the most Type-\(2\) vertices, containing \(k\) Type-\(2\) vertices and \(\Delta-2-k\) Type-\(3\) vertices. By assumption, there exists a part \(V_j\) which is non-adjacent to \(V_i\). Then \(V_j\) contains at most \(k\) Type-\(2\) vertices and at least \(\Delta-2-k\) Type-\(3\) vertices.
The number of color classes in the graph is determined by the number of color classes of Type-\(1\) parts. By relabelling as needed, suppose there are at least \(\Delta/2\) types of color class \(2\), and let \(V_1\) be a Type-\(1\) part where \(c(V_1) = 2\). We can count the number of \((V_1,2)\)-triangles in two ways. We show by an average argument based on 19 that for certain \(k\) values, there must exist a part which contains at least \(\Delta/2\) vertices with color \(3\). When there are at least 3 parts of color class \(3\), this gives the required non-3-colorability conclusion by 20; we reach a similar conclusion when there are at most 2 parts of color class \(3\).
We count the number of \((V_1,2)\)-triangles in two ways. Firstly, since Type-\(2\) vertices cannot be adjacent by 16, to accommodate for the \(k\) Type-\(2\) vertices in \(V_i\), there must be at least \(k\) Type-\(3\) vertices in every non-Type-\(1\) part that is not \(V_i\) nor \(V_j\). By 15, \[\label{eqn:v12triangles1} \text{\# of (V_1,2)-triangles}\ge (\Delta-2-k) + k(\Delta/2-2),\tag{1}\] where the first term comes from \(V_i\) or \(V_j\) depending on their color class, and the second term comes from having at least \(k\) Type-\(3\) or Type-\(1\) vertices in each of the remaining \(\Delta/2-2\) parts of color class \(2\) (the \(-2\) term in \(\Delta/2-2\) comes from excluding \(V_1\), and one of \(V_i\) or \(V_j\)). Note that the Type-\(1\) parts actually contribute \(\Delta-2\) many \((V_1,2)\)-triangles, but for our purposes, \(k\) suffices.
Secondly, each non-Type-\(1\) part that is not \(V_i\) nor \(V_j\) contains at least \(\Delta-2-k\) Type-\(3\) vertices by choice of \(k\). Each Type-\(1\) part contains \(\Delta-2\) Type-\(1\) vertices, and therefore at least \(\Delta-2-k\) Type-\(1\) vertices. By 15, \[\label{eqn:v12triangles2} \text{\# of (V_1,2)-triangles}\ge (\Delta-2-k)(\Delta/2-1).\tag{2}\] We split into three cases based on the value of \(k\).
5.0.0.1 Case 1: \(k\ge \Delta/2 + 2\).
By 19 and 1 , there is a part of color class \(3\) which contains at least \[\displaystyle\frac{(\Delta-2-k) + k(\Delta/2-2)}{\Delta/2} \ge \frac{(\Delta/2+2)(\Delta/2-2)}{\Delta/2} = \frac{\Delta}{2} - \frac{8}{\Delta}\] vertices with color \(3\). As this quantity is integer and since \(\Delta\ge 17\), we conclude that there are at least \(\Delta/2\) vertices with color \(3\) in one part.
Since each part contains \(\Delta-2\) elements, we have the required conclusion if there are at least three parts of color class \(3\) by 20. If there are at most two parts of color class \(3\), then there must be at least (using 1 again) \[(\Delta-2-k) + k(\Delta/2-2) \ge (\Delta/2+2)(\Delta/2-2) = \Delta^2/4 -4\] vertices with color \(3\). But there can be at most \(2\Delta-4\) vertices with color \(3\). Since \(\Delta\ge 17\), we have \(\Delta^2/4 -4> 2\Delta-4\). So this case is also not \(3\)-colorable.
5.0.0.2 Case 2: \(k\le \Delta/2 -3\).
By 19 and 2 , there is a part of color class \(3\) which contains at least \[\displaystyle\frac{(\Delta-2-k)(\Delta/2-1)}{\Delta/2} \ge \frac{(\Delta/2+1)(\Delta/2-1)}{\Delta/2} = \frac{\Delta}{2} - \frac{2}{\Delta}\] vertices with color \(3\). As this quantity is integer and since \(\Delta\ge 17\), we conclude that there are at least \(\Delta/2\) vertices with color \(3\) in one part. Since each part contains \(\Delta-2\) elements, we have the required conclusion if there are at least three parts of color class \(3\) by 20. If there are at most two parts of color class \(3\), then there must be at least (using 2 again) \[(\Delta-2-k)(\Delta/2-1) \ge (\Delta/2+1)(\Delta/2-1) = \Delta^2/4 -1\] vertices with color \(3\). But there can be at most \(2\Delta-4\) vertices with color \(3\). Since \(\Delta\ge 17\), we have \(\Delta^2/4 -1> 2\Delta-4\). So this case is also not \(3\)-colorable.
5.0.0.3 Case 3: \(\Delta/2-2 \le k \le \Delta/2+1\).
Noting that \(\deg(x_i) = \Delta\), we consider the canonical partition of \(N_2\) rooted at \(x_i\). \(V_i\) contains \(k\) Type-\(2\) vertices; each of these vertices have a Type-\(1\) part corresponding to it in the new partition. In this new partition, we shall reuse the notation \(V_1,V_2,\ldots, V_\Delta\). By relabelling as needed, suppose there are at least \(\Delta/2\) types of color class \(2\), and let \(V_1\) be a Type-\(1\) part where \(c(V_1) = 2\).
We count the number of \((V_1,2)\)-triangles. There are exactly \(k\) Type-\(1\) parts, which means that at least \(k/2\) of these parts are of color class \(2\). From these parts, we pick up a contribution of \((k/2-1)(\Delta-2)\). The \(-1\) term in the \(k/2-1\) expression comes from excluding \(V_1\).
On the other hand, there are exactly \(\Delta-k\) non-Type-\(1\) parts. Let \(V_k\) be a non-Type-\(1\) part with the most number \(j\) of Type-\(2\) vertices. Let \(V_\ell\) be its non-adjacent part. If \(j\le\Delta/2\), then all non-Type-\(1\) parts contain at least \(\Delta/2\) Type-\(3\) vertices by maximality of \(j\). On the other hand, if \(j\ge \Delta/2\), then all non-Type-\(1\) parts which are adjacent to \(V_k\) must have at least \(j\) Type-\(3\) vertices by 16. This means that on average, each non-Type-\(1\) part of color class \(2\) has at least \(\Delta/2-1\) Type-\(3\) vertices. Indeed, one can match the \(\Delta-2-j\) Type-\(3\) vertices of \(V_k\) (or of \(V_\ell)\) with the \(j\) Type-\(3\) vertices of an adjacent part of color class \(2\). Such a match exists since \(\Delta-k\ge \Delta/2-1\), which means there are at least 8 non-Type-\(1\) parts as \(\Delta\ge 17\). To conclude, we obtain a contribution of at least \(((\Delta-k)/2)(\Delta/2-1)\) many \((V_1,2)\)-triangles.
By 19, there is a part of color class \(3\) with at least \[\frac{(k/2-1)(\Delta-2) + ((\Delta-k)/2)(\Delta/2-1)}{\Delta/2}\] vertices with color \(3\). It is routine to show that this number is at least \(\Delta/2\) when \(\Delta\ge 17,15,13,11\) when \(k=\Delta/2-2, \Delta/2-1, \Delta/2, \Delta/2 + 1\), respectively. Since \(\Delta\ge 17\), this means that the graphs in this case are not \(3\)-colorable. ◻
We summarize the results obtained in this section.
Theorem 29. Let \(G\) be a \(C_4\)-free graph of diameter-\(2\) with no universal vertex, where \(\Delta(G)\ge17\). Suppose \(G\) is not isomorphic to a Moore graph of degree-\(57\). Then \(G\) is not \(3\)-colorable.
Proof. Let \(v_0\) be a vertex with \(\deg(v_0) = \Delta = \Delta(G)\), and let \(N_2 = N_2(v_0)\). Since there is no universal vertex, \(N_2\ne \emptyset\). Every vertex in \(N_2\) is of Type-\(1\), Type-\(2\), or of Type-\(3\) by 10. By 14, if there is either a Type-\(1\) or a Type-\(2\) vertex, then we may always assume that there is a Type-\(1\) part in the canonical partition. Furthermore, every part is of the same cardinality (7) and every part has \(\Delta-2\) or \(\Delta-1\) elements (8). We have exhaustively checked that when each part contains \(\Delta-2\) elements, the graph is not \(3\)-colorable ([lem:T1Delta-2,lem:ColorT1andT2,lem:ColorT3,lem:ColorT1T3,lem:ColorT1T2T3]). On the other hand, if each part contains \(\Delta-1\) elements, then \(G\) must contain only Type-\(1\) parts (9). In that case, \(G\) must be isomorphic to a Moore graph (27). Moore graphs have degree\(2,3,7\), or \(57\) [15]. By assumption, \(\Delta\ge17\) and \(G\) is not isomorphic to a Moore graph of degree-\(57\), so these cases do not occur. This proves the claim. ◻
6 Proof of [thm:main]↩︎
We are now ready to prove [thm:main].
Proof. Let \(G\) be a \(C_4\)-free graph of diameter-\(2\). If \(N_2=\emptyset\), then we can solve the instance in polynomial-time by 2. So suppose \(N_2\ne \emptyset\). By 29, all graphs with maximum diameter at least \(17\), excluding Moore graphs of degree-\(57\), are not \(3\)-colorable. The list \(3\)-colorability of Moore graphs of degree-\(57\) can be computed in constant time by 27. The list \(3\)-colorability of the remaining finitely many graphs with maximum degree at most \(16\) can be hardcoded into a lookup table. One can determine the maximum degree in polynomial-time, and thus deciding if \(G\) is list \(3\)-colorable can be solved in polynomial-time. ◻
7 Discussion↩︎
We showed that List \(3\)-Coloring \(C_4\)-free Diameter-\(2\) is polynomial-time solvable. It turns out that many \(C_4\)-free graphs of diameter-\(2\) with maximum degree at least \(17\) are not \(3\)-colorable (29).
The key ingredient was the rigid structure arising from the \(C_4\)-free and diameter-\(2\) conditions. By anchoring on a vertex \(v_0\) of maximum degree \(\Delta\), one can show that every vertex in the network must be of degree \(\Delta\) or \(\Delta-1\). Furthermore, one can partition the vertices which are distance-\(2\) away from \(v_0\) into \(\Delta\) parts. Each part contains the same number of vertices and if they are adjacent, the vertices form a perfect matching.
The \(\Delta\ge 17\) condition for non-\(3\)-colorability arose from ensuring an impossible number of vertices of a certain color in the proof of 28. Interestingly, it was only needed in one part of the proof; the other parts required weaker conditions on \(\Delta\). Furthermore, non-\(3\)-colorability was shown for \(\Delta\ge 4\) in all other results in the same section ([lem:T1Delta-2,lem:ColorT1andT2,lem:ColorT3,lem:ColorT1T3]). So a natural question is to ask if we can strengthen the \(\Delta\ge 17\) result to \(\Delta\ge 4\). An affirmative answer would imply that the only \(C_4\)-free graphs of diameter-\(2\) with \(N_2\ne \emptyset\) are the three leftmost graphs in 1, together with a Moore graph of degree-\(57\) (the Hoffman-Singleton graph has chromatic number \(4\) [16]).
Problem 30. Let \(G\) be a \(C_4\)-free graph of diameter-\(2\) with \(\Delta(G)\ge4\). Suppose \(G\) is not isomorphic to a Moore graph of degree-\(57\). Show that \(G\) is not \(3\)-colorable.
In another direction, one can ask if the so-called diamond elimination of [4] preserves induced \(C_4\)-freeness.
Reduction Rule 1 (Diamond Elimination). If the quadruple \(\{u_1,u_2,u_3,u_4\}\) of vertices in \(G\) induces a diamond graph, where \(u_1u_2\notin E\), then merge vertices \(u_1\) and \(u_2\).
This is not immediately clear (see 4). An affirmative answer would allow one to strengthen the ‘\(C_4\)-free’ condition to the ‘induced \(C_4\)-free’ condition. It should be noted that the graph shown in 4 is of diameter-\(3\).
Problem 31. Let \(G\) be an induced \(C_4\)-free graph of diameter-\(2\). Let \(G'\) be the graph obtained by applying 1 exhaustively to \(G\). Is \(G'\) induced \(C_4\)-free?
Finally, the problem remains open when we replace the \(C_4\)-free condition by the \(C_3\)-free condition, or if we remove the \(C_4\)-free condition outright. A natural question is to ask if any of the structural results of 3 remain true. The answer is a definitive no. 3, which states that every vertex in \(N_2\) has exactly one neighbour in \(N_1\) already breaks, as the ‘exactly’ becomes ‘at least’. So vertices in \(N_2\) cannot be partitioned based on their adjacencies to \(N_1\), which means that the canonical partition would no longer exist. A new strategy is most likely needed to tackle these problems.
Acknowledgements↩︎
The author thanks Carla Groenland, Ananthakrishnan Ravi, and Nikolaas Verhulst for helpful discussions on \(3\)-coloring graphs of bounded degree. The author thanks Dion Gijswijt for a helpful discussion on diamond elimination.
References↩︎
A claw is the graph \(K_{1,3}\). A center of a claw is the vertex with degree-\(3\). A graph is quasi-claw-free is for any two vertices \(x,y\) which are distance-\(2\) apart, there exists a common neighbour \(z\) such that all neighbours of \(z\) (excluding \(x,y\)) are neighbours of \(x\) or \(y\).↩︎
Note that this is different from List \(2\)-Coloring. Here, lists do not have to be subsets of \(\{1,2\}\), but they are subsets of size \(2\).↩︎