Let \(G\) be a plane graph. If two edges are adjacent and consecutive on the boundary walk of a face of \(G\), then they are said to be facially adjacent. We call \(G\) facially entire \(k\)-colorable if there is a mapping from \(V(G)\cup E(G)\cup F(G)\) to a \(k\) color set so that any two facially adjacent edges, adjacent vertices, adjacent faces, and incident elements receive different colors. The facial entire chromatic number of \(G\) is defined to be the smallest integer \(k\) such that \(G\) is facially entire \(k\)-colorable. In 2016, Fabrici, Jendrol’ and Vrbjarová conjectured that every connected, loopless, bridgeless plane graph is facially entire \(7\)-colorable. In this paper, we give a positive answer to this conjecture for \(K_4\)-minor-free graphs. More specifically, we shall prove that every \(K_{4}\)-minor-free graph is facially entire \(7\)-colorable.
Throughout our paper, we only consider finite, simple and undirected graphs. A graph \(G\) is called planar if it can be embedded in the plane such that any two edges intersect only at their ends. For a plane graph \(G\), let \(V(G)\), \(E(G)\), \(F(G)\), \(|E(G)|\), \(\delta(G)\) and \(\Delta(G)\) denote the vertex set, edge set, face set, size, minimum degree and maximum degree of \(G\), respectively. For \(v\in V(G)\), let \(d_G(v)\) denote the degree of \(v\) in \(G\) and call \(v\) a \(k\)-vertex if \(d(v)=k\) and a \(k^+\)-vertex if \(d(v)\ge k\). For a face \(f\in F(G)\), we use \(b(f)\) to denote its boundary walk and write \(f=[v_{1}v_{2}\ldots v_{n}]\) if \(v_{1},v_{2},\ldots,v_{n}\) are lying on \(b(f)\).
An entire \(k\)-coloring of a plane graph \(G\) is a mapping \(\pi\): \(V(G)\cup E(G)\cup F(G)\rightarrow\{1,2,\ldots,k\}\) such that any two adjacent or incident elements in \(V(G)\cup E(G)\cup F(G)\) receive distinct colors. The entire chromatic number, denoted \(\chi_{vef}(G)\), of \(G\) is the least integer \(k\) such that \(G\) has an entire \(k\)-coloring. This concept was first introduced in [6] by Kronk and Mitchem who conjectured that every simple plane graph is entirely (\(\Delta(G)+4\))-colorable. Moreover, in the same paper, the authors positively confirmed this conjecture for \(\Delta(G)\le 3\). We notice that for a complete graph \(K_4\), \(\chi_{vef}(K_{4})=7=\Delta(G)+4\), and thus the bound \(\Delta(G)+4\) is tight. In 1989, Borodin [1] affirmed the conjecture for \(\Delta(G)\ge 12\), and later strengthened this to \(\Delta(G)\ge 7\) in [2]. Sanders and Zhao [8] further provided a proof of \(\Delta(G)\ge 6\) for the conjecture. However, there is a mistake in [11] which has been corrected by Wang and Zhu [11]. Finally, Wang and Zhu [11] positively settled the whole conjecture.
As a relaxation of the entire coloring of plane graphs, the concept of the facial entire coloring of plane graphs was first investigated by Fabrici, Jendrol’ and Vrbjarová [5] in 2016. Let \(G\) be a plane graph. Two edges \(e_1, e_2\in E(G)\) are called facially adjacent if they are adjacent and consecutive on the boundary walk of a face of \(G\). A facial entire \(k\)-coloring of \(G\) is a mapping \(\pi\) from \(V(G)\cup E(G)\cup F(G)\) to a \(k\) color set \(\{1,2,\ldots,k\}\) such that any two facially adjacent edges, adjacent vertices, adjacent faces, and incident elements in \(V(G)\cup E(G)\cup F(G)\) receive distinct colors. The facial entire chromatic number, denoted \(\bar{\chi}_{vef}(G)\), of \(G\) is the smallest integer \(k\) such that \(G\) has a facial entire \(k\)-coloring. It is obvious that \(\bar{\chi}_{vef}(G)\le \chi_{vef}(G)\). Moreover, the parameter \(\bar{\chi}_{vef}(G)\) is independent on \(\Delta(G)\). The reader is referred to [3, 4, 9, 10, 12] for some results on edge-face coloring and facially edge-face coloring.
Fabrici, Jendrol’ and Vrbjarová [5] showed us that \(\bar{\chi}_{vef}(G)\le 8\) for any connected, loopless and bridgeless plane graph \(G\). Moreover, in [5], they characterized the facial entire chromatic number of wheel graphs, and put forward the following conjecture.
Conjecture 1.1. Every connected, loopless and bridgeless plane graph is facially entire \(7\)-colorable.
As far as we know, Conjecture 1.1 is widely open. In this paper, we focus on studying the facial entire coloring of \(K_{4}\)-minor-free graphs. A graph \(H\) is said to be a minor of a graph \(G\) if \(H\) can be obtained from \(G\) by a series of vertex deletions, edge deletions, and edge contractions. Further, \(G\) is called \(H\)-minor-free if \(G\) does not contain \(H\) as a minor. It is known that the class of \(K_4\)-minor free graphs is a special type of planar graphs.
For \(u, v\in V(G)\), The distance between \(u\) and \(v\), denoted \(d_G(u,v)\), is the length of a shortest path connecting them. For convenience, let \(N_i(u)=\{v\mid v\in V(G)\) and \(d_G(u,v)=i\}\). Moreover, we let \(T(u,v)\) denote the set of all \(2\)-vertices in \(G\) which are adjacent to both \(u\) and \(v\). Let \(G\) be a \(K_{4}\)-minor-free graph. We define:
\(D_G(u)=\{v \mid d_{G}(v)\ge 3\) such that either \(uv\in E(G)\) or there is a \(2\)-vertex \(x\) such that \(ux, xv\in E(G)\}.\)
The following key structural lemma appeared in [7].
Lemma 2.1. Let \(G\) be a \(K_{4}\)-minor-free graph. Then \(G\) contains one of the following configurations (C1), (C2) and (C3).
(C1) \(\delta(G)\le 1\);
(C2) there exist two adjacent \(2\)-vertices;
(C3) there is a \(3^{+}\)-vertex \(u\) with \(|D_{G}(u)|\le2\) .
This section is devoted to establishing the main result of this paper.
Theorem 3.1. If \(G\) is a \(K_4\)-minor-free graph, then \(\bar{\chi}_{vef}(G)\le 7\).
Proof. We prove the theorem by induction on \(|E(G)|\). Let \(\mathcal{C}=\{1, 2, \ldots, 7\}\) denote a set of seven colors. W.l.o.g., we may assume that \(G\) is a connected graph embedded in the plane. If \(|E(G)|\le 3\), then \(\Delta(G)\le 3\), we deduce that \(\bar{\chi}_{vef}(G)\le \chi_{vef}(G)\le \Delta(G)+4\le 7\). So assume that \(G\) is a \(K_{4}\)-minor-free graph with \(|E(G)|\ge 4\). By Lemma 2.1, \(G\) contains one of the configurations (C1), (C2) and (C3). In each of following cases, we will construct a graph \(G^*\) such that \(|E(G^*)|<|E(G)|\). Firstly, we have the following:
Case 1. \(G\) is \(2\)-connected.
Proof. Suppose to the contrary that there exists a cut vertex \(v\in V(G)\) and let \(G_1\) and \(G_2\) be two connected subgraphs such that \(V(G_1)\cap V(G_2)=\{v\}\) and \(G_1\cup G_2=G\). Clearly, \(G_1\) and \(G_2\) are both connected \(K_{4}\)-minor-free graphs and have at least two vertices, respectively. For \(i=1,2\), by the induction hypothesis, each \(G_i\) admits a facial entire \(7\)-coloring, say \(\pi_i\). Now assume w.l.o.g., that \(d_{G_{1}}(v)=m\) and \(d_{G_{2}}(v)=k\) such that \(k\ge m\). Note that \(k\ge m\ge 1\).
Denote by \(f_1\) and \(f_2\) the outer faces of \(G_1\) and \(G_2\), respectively. For convenience, we use \(v_{11}, \ldots, v_{1m}\) to denote all neighbors of \(v\) in \(G_1\) such that \(vv_{11}\) and \(vv_{1m}\) are lying on the boundary of \(f_1\). Similarly, let \(v_{21},\ldots, v_{2k}\) denote all neighbors of \(v\) in \(G_2\) such that \(vv_{21}\) and \(vv_{2k}\) are lying on the boundary of \(f_2\). First permute the colors in \(G_2\) such that \(\pi_2(v)=\pi_1(v)\) and \(\pi_2(f_2)=\pi_1(f_1)\). We have to discuss two cases in light of the value of \(m\) and \(k\).
\(\bullet\) \(m=1\).
Notice that it might be the case that \(k=1\). If \(\pi_2(vv_{21}) \ne \pi_1(vv_{11})\) and \(\pi_2(vv_{2k}) \ne \pi_1(vv_{11})\), then \(\pi_1\cup \pi_2\) is just a facial entire 7-coloring of \(G\). Otherwise, w.l.o.g., assume that \(\pi_2(vv_{21})=\pi_1(vv_{11})\). Then we can switch the colors \(\pi_2(vv_{21})\) and \(\alpha\in \mathcal{C}\setminus \{\pi_1(vv_{11}), \pi_2(v),\pi_2(f_2), \pi_2(vv_{2k})\}\). One may verify that the obtained coloring of \(G\) is a facial entire 7-coloring.
\(\bullet\) \(m\ge 2\).
Then \(k\ge 2\). Similarly, if \(\pi_2(vv_{21})\ne \pi_1(vv_{11})\) and \(\pi_2(vv_{2k})\ne \pi_1(vv_{1m})\), then \(\pi_1\cup \pi_2\) itself is a facial entire 7-coloring of \(G\). Otherwise, assume w.l.o.g., that \(\pi_2(vv_{21})=\pi_1(vv_{11})\). Noting that \(\pi_2(vv_{2k})\ne \pi_2(vv_{21})\), in order to establish a facial entire 7-coloring of \(G\), it suffices to switch colors \(\pi_2(vv_{21})\) and \(\pi_2(vv_{2k})\) in \(G_2\). ◻
Given a partial facial entire coloring \(\pi\) of \(G\) and an uncolored element \(x\in V(G)\cup E(G)\cup F(G)\), let \(F(x)\) denote the set of colors forbidden to use on \(x\), and let \(f(x)=|F(x)|\). By Claim 1, we are sure that \(G\) does not contain (C1).
Case 1. \(G\) contains (C2): two adjacent 2-vertices \(u\) and \(v\).
Let \(u_1\) denote the neighbor of \(u\) other than \(v\), and \(v_1\) the neighbor of \(v\) other than \(u\). We have two subcases below.
Subcase 1.1. \(u_1=v_1\).
Write \(u_1=v_1=u^*\). Then \(uvu^*u\) is a 3-cycle. By Claim 1, we ensure that \(u^*\) is a 2-vertex, implying that \(|E(G)|=3\), which contradicts the assumption that \(|E(G)|\ge 4\).
Subcase 1.2. \(u_1\ne v_1\).
Let \(G^*\) be a graph obtained from \(G\) by contracting the edge \(uv\) into a new vertex \(w\). Obviously, \(G^*\) is a \(K_4\)-minor-free graph with \(|E(G^*)|<|E(G)|\). By the induction hypothesis, \(G^*\) has a facial entire \(7\)-coloring \(\pi^*\) by using the color set \(\mathcal{C}\).
To extend \(\pi^*\) to the graph \(G\), we first assign \(\pi^*(u_1w)\) to \(u_1u\), \(\pi^*(v_1w)\) to \(v_1v\), and \(\pi^*(w)\) to \(v\). Then we color \(uv\) and \(u\) in order with a color in \(\mathcal{C}\setminus F(uv)\) and \(\mathcal{C}\setminus F(u)\), respectively. This is available because \(f(uv)\le 5\) and \(f(u)\le 5\).
Case 2. \(G\) contains (C3): There is a \(3^{+}\)-vertex \(u\) with \(|D_{G}(u)|\le 2\).
By the proof of Case 1, we may assume that \(|D_{G}(u)|\ge 1\). Let \(d_G(u)=k\) and denote \(u_1, u_2, \ldots, u_k\) be adjacent to \(u\) in cyclic order. It remains us to deal with two subcases in terms of \(|D_{G}(u)|\).
Subcase 2.1. \(|D_{G}(u)|=1\), say \(D_G(u)=\{v\}\).
It means that all neighbors of \(u\) are either \(v\) or some neighbors of \(v\). Namely, \(v\in N_1(u)\cup N_2(u)\). The following claims will be helpful in the rest of our paper.
Claim 2. Let \(u\) be a \(3^+\)-vertex in \(G\) and let \(u_1, u_2, \ldots, u_{d_G(u)}\) consecutively be adjacent to \(u\). If there exist a \(3^+\)-vertex \(u_{i}\) and a \(2\)-vertex \(u_{i+1}\) such that \([uu_iu_{i+1}]\) is a \(3\)-face, then \(G\) is facially entire \(7\)-colorable.
Proof. Let \(G^*=G-u_{i+1}\). Then \(G^*\) is a \(K_4\)-minor-free graph and \(|E(G^{*})|<|E(G)|\). By the induction hypothesis, \(G^*\) has a facial entire \(7\)-coloring \(\pi^{*}\) by using \(\mathcal{C}\). Since \(f([uu_iu_{i+1}])\le 5\), \(f(uu_{i+1})\le 4\), \(f(u_{i}u_{i+1})\le 4\) and \(f(u_{i+1})\le 3\), one may color \([uu_iu_{i+1}]\), \(uu_{i+1}\), \(u_{i}u_{i+1}\), and \(u_{i+1}\) in succession. It is easy to check that the obtained coloring of \(G\) is a facial entire 7-coloring and thus we are done. ◻
Claim 3. Let \(u\) be a \(3^+\)-vertex in \(G\) and let \(u_1, u_2, \ldots, u_{d_G(u)}\) consecutively be adjacent to \(u\). If there exists a vertex \(v\notin N_1(u)\) such that \(d_G(u_{i})=d_G(u_{i+1})=2\) and \([uu_ivu_{i+1}]\) is a \(4\)-face, then \(G\) is facially entire \(7\)-colorable.
Proof. Let \(G^*=G-\{u_{i},u_{i+1}\}+uv\). Obviously, \(G^*\) is a \(K_4\)-minor-free graph with \(|E(G^{*})|<|E(G)|\). Thus, \(G^*\) has a facial entire \(7\)-coloring \(\pi^{*}\) by the induction hypothesis. We will show how to extend \(\pi^*\) to the whole graph \(G\).
First, assign \(\pi^*(uv)\) to both \(uu_i\) and \(u_{i+1}v\). Then, one can color \([uu_ivu_{i+1}]\), \(uu_{i+1},u_{i}v, u_{i}\) and \(u_{i+1}\) in order successfully due to the fact that \(f([uu_ivu_{i+1}])\le 5\), \(f(uu_{i+1})\le 4\), \(f(u_{i}v)\le 4\) and \(f(u_{i})=f(u_{i+1})=4\). Thus, \(G\) is facially entire \(7\)-colorable. ◻
The following proof of Subcase 2.1 is divided into two cases below, according to the situation of \(v\).
\(\bullet\) \(v\in N_1(u)\).
W.l.o.g., assume that \(v=u_1\). Then \(d_G(u_i)=2\) for all \(i=2,3,\ldots, k\), and thus \(T(u,v)=\{u_2, \ldots, u_k\}\). By Claim 1, we are sure that \(v\) cannot be adjacent to any other vertices apart from \(u, u_2, \ldots, u_k\). This guarantees us that \(G\) has been fixed, as depicted in the left configuration of Figure 1.
For this case, we notice that \(u\) and \(v\) are both \(3^{+}\)-vertices, and \(u_{2}\) is a 2-vertex such that \([uvu_2]\) is a 3-face. So by Claim 2, one can conclude that \(G\) is facially entire 7-colorable.
\(\bullet\) \(v\in N_2(u)\).
Then \(uv\notin E(G)\). It follows immediately that \(T(u, v)=\{u_1, \ldots, u_k\}\). By Claim 1, neither \(u\) nor \(v\) can be a cut vertex, and hence \(G\) has been fixed, as shown in the right configuration of Figure 1.
At this moment, we observe that both \(u\) and \(v\) are \(3^+\)-vertices, and \(d_G(u_{1})=d_G(u_{2})=2\) such that \([uu_1vu_2]\) is a 4-face. Moreover, \(uv\notin E(G)\). Consequently, \(G\) is facially entire 7-colorable by Claim 3.
Subcase 2.2. \(|D_{G}(u)|=2\), say \(D_G(u)=\{v,w\}\).
It follows that \(d_G(v)\ge 3\) and \(d_G(w)\ge 3\). Moreover, the neighbors of \(u\) is either \(v\), or \(w\), or a 2-vertex that is adjacent to \(v\) or \(w\). That is, \(v, w\in N_{1}(u)\cup N_{2}(u)\). To obtain a facial entire 7-coloring of the graph \(G\), we have to consider three possibilities according to the situations of \(v\) and \(w\).
\(\bullet\) \(N_{2}(u)=\{v,w\}\).
Then \(uv\notin E(G)\) and \(d_G(u_i)=2\) for all \(i=1,2,\ldots, k\). By the planarity of \(G\), assume w.l.o.g., that \(T(u,v)=\{u_1, \ldots, u_j\}\) and \(T(u,w)=\{u_{j+1}, \ldots, u_k\}\), and suppose that \(j\ge 2\) due to \(k\ge 3\). Note that \([uu_1vu_2]\) (if \(j=2\) then \(u_2=u_j\)) is a 4-face; otherwise, \(v\) has some neighbor inside of the 4-cycle \(uu_1vu_2u\) and thus \(v\) becomes a cut vertex of \(G\), which contradicts Claim 1. Hence, by Claim 3, \(G\) is facially entire 7-colorable.
\(\bullet\) \(N_1(u)=\{v, w\}\).
As \(k\ge 3\), we have that either \(|T(u,v)|\ge 1\) or \(|T(u,w)|\ge 1\). W.l.o.g., assume that \(|T(u,v)|\ge 1\). It implies that there is a 2-vertex \(u_{i}\in T(u,v)\) such that \([uu_{i}v]\) is a 3-face, and therefore \(G\) is facially entire 7-colorable by applying Claim 2.
\(\bullet\) By symmetry, suppose that \(v\in N_1(u)\) and \(w\in N_2(u)\).
If \(T(u,v)\ne \emptyset\), then there exists a 2-vertex \(u_{i}\in T(u,v)\) such that \([uu_iv]\) is a 3-face. Hence, by Claim 2, \(G\) is facially entire 7-colorable. Otherwise, assume that \(|T(u,w)|\ge 2\). Namely, there are consecutive two 2-vertices, say \(u_j, u_{j+1}\in T(u,w)\), so that \([uu_{j}wu_{j+1}]\) is a 4-face. By Claim 3, we conclude that \(G\) is facially entire 7-colorable.
This completes the proof of Theorem 3.1. ◻
This research was supported by the Zhejiang Natural Science Foundation of China (Grant Nos. LZ23A010004, LR25A010002) and the National Natural Science Foundation of China (Grant No. 12371360).