Weakly edge-face coloring of Halin graphs

Abstract

Let G=(V,E,F) be a connected loopless plane graph, with vertex set V, edge set E, and face set F. For any adjacent faces e₁ and e₂, if they are incident to the same face and appear consecutively on the edge of that face, then it is said that e₁ and e₂ are facially adjacent. A plane graph G is called weakly edge-face k-colorable indicating that there is a mapping \pi :E\cup F\to\{1,2,\dots ,k\} such that any two incident edges and faces, adjacent faces, and facially adjacent edges receive distinct colors. The weakly edge-face chromatic number of G, denoted by {\overline{\chi }}_{ef}\left(G\right), is defined to be the smallest integer k such that G has a weakly edge-face k-coloring. In 2016, Fabrici conjectured that every connected, loopless, and bridgeless plane graph was weakly edge-face 5-colorable. In this paper, a sufficient condition is provided for the foregoing conjecture to prove that Halin graphs are weakly edge-face 5-colorable in which the upper bound 5 is the best possible.

Graphical abstract

Keywords

Halin graph / wheel graph / weakly edge-face coloring / weakly edge-face chromatic number

1 Introduction

All graphs considered in this paper are loopless connected graphs. Suppose G is a graph. If G can be drawn on a plane such that its edges intersect only at their vertices, then G is called a planarizable graph. Such drawing of the graph on a plane is called a planar embedding of the graph, or simply a plane graph. For a plane graph G, V\left(G\right), E\left(G\right), F\left(G\right), and \mathrm{\Delta }\left(G\right) are used to denote the vertex set, edge set, face set, and maximum degree of G, respectively. Halin graph G=T\cup C is a plane graph, where T is a tree with a maximum degree of at least 3 and no vertices of degree 2, and C is a cycle formed by connecting the vertices of degree 1 in T in the order of the planar embedding. A wheel graph is a special type of Halin graph. W_n=K_1+C_{n-1} is used to denote the wheel graph of order n.

The edge-face coloring problem of plane graphs was first studied independently by Jucovič [7] (1969) and Fiamčík [5] (1971). Let G be a plane graph. If k colors can be used to color the adjacent edges, adjacent faces, and incident edge and face of G with different colors, then G is said to be edge-face k-colorable. The edge-face chromatic number of G, denoted as {\chi }_{e}f\left(G\right), is defined as the minimum positive integer k such that G is edge-face k-colorable.

In 1975, Melnikov [8] proposed the conjecture that every plane graph G was edge-face (∆(G) + 3)-colorable. This conjecture was independently proven to be true by Waller [13], Sanders and Zhao [9], and Wang and Lih [14] successively. After Melnikov's conjecture was proven, Sanders and Zhao [11] proposed a stronger conjecture in 2001: every plane graph G was edge-face (\mathrm{\Delta }(G)+2)-colorable. It was verified that the conjecture held for \mathrm{\Delta }\left(G\right)\le 3 and \mathrm{\Delta }\left(G\right)\ge 7 in references [10] and [11], respectively. In 2014, Chen et al. [2] completely solved the case of \mathrm{\Delta }\left(G\right)=6. Therefore, the cases of \mathrm{\Delta }\left(G\right)=4 and \mathrm{\Delta }\left(G\right)=5 remain challenging problems at present. Regarding Halin graphs, Gong and Wu [6] proved that if 3\le \mathrm{\Delta }\left(G\right)\le 5, then {\chi }_{ef}\left(G\right)\le 5; if \mathrm{\Delta }\left(G\right)\ge 6, then {\chi }_{ef}\left(G\right)=\mathrm{\Delta }\left(G\right).

In recent years, based on edge-face coloring [12], Fabrici et al. [4] proposed a new coloring concept, namely, the weakly edge-face coloring of plane graphs. For any two adjacent edges e₁ and e₂, if they are incident to the same face and appear consecutively on the edge of that face, then e₁ and e₂ are said to be face adjacent. A graph G is weakly edge-face k-colorable indicating that there exists a mapping \pi :E\cup F\to \{1,\dots ,k\} such that any two incident edges and faces, adjacent faces, and face-adjacent edges receive distinct colors. The weak edge-face chromatic number of plane graph G, denoted as {\overline{\chi }}_{e}f\left(G\right), is the minimum value of k for which G is weakly edge-face k-colorable. Obviously, {\overline{\chi }}_{ef}\left(G\right)\le {\chi }_{ef}\left(G\right). When proposing the concept, Fabrici et al. [4] proved that connected, loopless, and bridgeless plane graphs were weakly edge-face 6-colorable and put forward the following conjecture.

Conjecture 1.1 [4]　 Every connected, loopless, and bridgeless plane graph is weakly edge-face 5-colorable. In addition, they also gave the weak edge-face chromatic number of wheel graphs.

Theorem 1.1 [4]　 For every wheel graph W_n, where n\ge 3, there is

{\overline{\chi }}_{ef}\left(W_n\right)=\{\begin{array}{ll}5,& n=2k+1,k\ge 1;\\ 4,& n=2k,k\ge 2.\end{array}

In this paper, we study the weak edge-face chromatic numbers of Halin graphs and obtain the following conclusions, which illustrates that Halin graphs satisfy Conjecture 1.1 and the upper bound 5 is optimal.

Theorem 1.2　 Halin graphs are weakly edge-face 5-colorable.

2 Lemmas and notations

Let G be a Halin graph. Suppose v\in V\left(G\right). The number of edges incident to v is called the degree of v, denoted as d_G\left(v\right). The set of all vertices adjacent to v is called the neighborhood of v in G, denoted as N_G\left(v\right). For convenience, the unbounded face formed by V(C) is called the outer face, denoted as f^o, and the remaining faces are called inner faces. The vertices in V\left(f^o\right) are called outer vertices, and the vertices in G-V\left(f^o\right) are called inner vertices. Denote the set of all inner vertices as V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right), that is V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right)=V\left(G\right)\mathrm{\setminus }V\left(f^o\right). We call the inner vertices adjacent to outer vertices special inner vertices. Obviously, there are at least two special inner vertices in Halin graphs (except wheel graphs). For any edge e\in E\left(f^o\right), denote the inner face incident to f^o at the edge e as f_e^o. Notations not defined in this paper are all cited from the book by Bondy and Murty [1].

In reference [3], Chen and Wang give a complete characterization of the structure of Halin graphs.

Lemma 2.1 [3]　 LetG=T\cup Cbe any Halin graph other than a wheel graph. ThenGmust contain one of the following three structures, as shown inFig. 1.

(A1) There exists a special inner 3-vertex v, an inner vertex u, and a path xv₁v₂y on C such that N_G\left(v\right)=\left\{v_1,v_2,u\right\} and uy\in E\left(G\right);

(A2) There exist special inner 3-vertices v, w, an inner vertex u, and a path xv₁v₂w₁w₂y on C such that N_G\left(v\right)=\{v_1,v_2,u\} and N_G\left(w\right)=\{w_1,w_2,u\};

(A3) There exists a special inner (t+1)-vertex v, an inner vertex u, and a path x{v}_1{v}_2\cdots v_{t}y on C such that N_G\left(v\right)=\{v_1,v_2,\dots ,v_t,u\}.

3 Proof of Theorem 1.2

Suppose G is a Halin graph. When \mathrm{\Delta }\left(G\right)\le 5, then {\overline{\chi }}_{ef}\left(G\right)\le {\chi }_{ef}\left(G\right)\le 5. Therefore, in the following, it is assumed that \mathrm{\Delta }\left(G\right)\ge 6. Mathematical induction on \left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right)\right| is used to complete the proof of Theorem 1.2.

When \left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right)\right|=1, G is a wheel graph. By Theorem 1.1, {\overline{\chi }}_{ef}\left(G\right)\le 5, so Theorem 1.2 holds. Now it is assumed that when \left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right)\right|=k, where k ≥ 2, Theorem 1.2 holds. Next, consider the case when \left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right)\right|=k+1. Denote the color set C=\{1,2,\dots ,5\}. According to Lemma 2.1, the following three cases are discussed.

Case 1: G contains the structure (A1).

Let G^{\ast }=G-\{v_1,v_2\}+\{xv,yv\}. Obviously, G* is a Halin graph, satisfying \mathrm{\Delta }\left(G^{\ast }\right)=\mathrm{\Delta }\left(G\right), and \left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\right(G^{\ast }\left)\right|=\left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\right(G\left)\right|-1=k. According to the induction hypothesis, G* has a weak edge-face 5-coloring π*. Denote the outer face of G* as *, and the face incident to f* at the edge e as f_e^{\ast }. Next, extend π* to G so that G has a weak edge-face 5-coloring π. Without losing generality, assume {\pi }^{\ast }\left(f^{\ast }\right)=1. Denote \mathcal{A}=\{x{v}_1,f_{x{v}_1}^o,y{v}_2,f_{y{v}_2}^o\} and S=\{v{v}_1,v_1{v}_2,v{v}_2,f_{v_1{v}_2}^o\}.

Firstly, let \pi \left(f^o\right)=1. Secondly, assign the colors of xv,f_{xv}^{\ast },yv,f_{yv}^{\ast } in G* to the corresponding elements x{v}_1,f_{x{v}_1}^o,y{v}_2,f_{y{v}_2}^o in G. Then, let \pi \left(s\right)={\pi }^{\ast }\left(s\right), where s\in E\left(G\right)\cup F\left(G\right)\mathrm{\setminus }\left(\mathcal{A}\cup S\cup \left\{f^o\right\}\right). Next, it requires to show that the elements in S can also be properly colored so that G is weakly edge-face 5-colorable. For convenience, denote y^{\prime }\in N_G\left(y\right)\mathrm{\setminus }\{v_2,u\}. Let u{u}^{\prime },u{u}^{″} be face adjacent to the edges uv, uy, respectively. It should be noted that when d_G\left(u\right)=3, u^{\prime } and u^{″} coincide. π(A) is used to represent the set of colors of all elements in A at G. Obviously, 2\le \left|\pi \left(\mathcal{A}\right)\right|\le 4 and1\notin \pi \left(\mathcal{A}\right). We will discuss it in three sub-cases according to the value of \left|\pi \left(\mathcal{A}\right)\right|.

Case 1.1: \left|\pi \left(\mathcal{A}\right)\right|=4.

Without losing generality, assume that \pi \left(x{v}_1\right)=2, \pi \left(f_{x{v}_1}^o\right)=3, \pi \left(y{v}_2\right)=4, and \pi \left(f_{y{v}_2}^o\right)=5. This implies that \pi \left(uv\right)=1. It requires to color vv₁ with color 5, v₁v₂ with color 3, vv₂ with color 2, and f_{v_1{v}_2}^o with color 4. It is verified that the resulting coloring is a weakly edge-face 5-coloring of G.

Case 1.2: \left|\pi \left(\mathcal{A}\right)\right|=3.

For the convenience, denote s_1=v{v}_1,s_2=v_1{v}_2,s_3=v{v}_2, and s_4=f_{v_1{v}_2}^o, that is S=\{s_1,s_2,s_3,s_4\}. For any i\in \{1,2,3,4\}, let A(s_i) represent the set of available colors for the element s_i in G. Let A\left(\mathcal{S}\right)=\bigcup _{i=1} A\left(s_i\right). Assertion 3.1 is first introduced.

Assertion 3.1　 Assume \left|A\right(s_i\left)\right|=2(1\le i\le 4) and \left|A\left(S\right)\right|=4. If for any \{i,j,k\}\subseteq \{1,2,3,4\}, at most two of A(s_i), A(s_j), A(s_k) are the same, then there must exist a coloring {\pi }^{\prime }:S\to A\left(S\right) such that {\pi }^{\prime }\left(s_i\right)\in A\left(s_i\right)(1\le i\le 4) and for any s_i, s_j\in S satisfies {\pi }^{\prime }\left(s_i\right)\ne {\pi }^{\prime }\left(s_j\right).

Proof　Firstly, assume that there exist A(s_i) and A(s_j) such that A\left(s_i\right)=A\left(s_j\right). By symmetry, without losing generality, let A\left(s_1\right)=A\left(s_2\right)=\{a,b\}. According to the problem statement, A\left(s_3\right)\ne \{a,b\} and A\left(s_4\right)\ne \{a,b\}. This implies that there exist c_1\in A\left(s_3\right)\mathrm{\setminus }\{a,b\} and c_2\in A\left(s_4\right)\mathrm{\setminus }\{a,b\} such that c_1\ne c_2; otherwise, it can be deduced that \left|A\left(S\right)\right|=3, which contradicts the given conditions. At this point, it requires to color s₁, s₂, s₃, s₄ with colors a, b, c₁, c₂, respectively.

Secondly, assume that there exist A(s_i) and A(s_j) such that A\left(s_i\right)\cap A\left(s_j\right)=\varnothing. Without losing generality, let A\left(s_1\right)=\{a,b\} and A\left(s_2\right)=\{c,d\}. Further, by symmetry, it is assumed A\left(s_3\right)=\{a,c\}. If c\notin A\left(s_4\right), then color s₃ with c, s₂ with d, s₄ with \alpha \in A\left(s_4\right)\mathrm{\setminus }\{c,d\}, and s₁ with \beta \in A\left(s_1\right)\setminus \left\{\alpha \right\}. If c\in A\left(s_4\right), then it can be deduced that A\left(s_4\right)=\{b,c\}, and then color s₁, s₂, s₃, s₄ with a, d, c, b, respectively.

Finally, it is assumed that for any \{i,j\}\subset \{1,2,3,4\}, \left|A\left(s_i\right)\cap A\left(s_j\right)\right|=1. Since \left|A\left(S\right)\right|=4, it is not difficult to deduce that |A\left(s_1\right)\cap A\left(s_2\right)\cap A\left(s_3\right)\cap A\left(s_4\right)|=0. Therefore, according to the principle of inclusion-exclusion

it is known

This contradicts the fact , thus completing the proof of Assertion 3.1. □

Next, according to the positional relationship, consider Case 1.2.1 and Case 1.2.2.

Case 1.2.1: \pi \left(x{v}_1\right)=\pi \left(f_{y{v}_2}^o\right).

Without losing generality, assume \pi \left(x{v}_1\right)=\pi \left(f_{y{v}_2}^o\right)=2, \pi \left(f_{x{v}_1}^o\right)=3, and \pi \left(y{v}_2\right)=4. It is found that the color of the edge uv is either 1 or 5. If \pi \left(uv\right)=5, color s₁ with color 4, s₂ with color 3, s₃ with color 1, and s₄ with color 5. Now consider the case when \pi \left(uv\right)=1.

Case 1.2.1a: \pi \left(f_{y{y}^{\prime }}^o\right)\ne 5 and \pi \left(uy\right)\ne 5.

Change the color of f_{y{v}_2}^o to 5, and there are A\left(s_1\right)=\{4,5\}, A\left(s_2\right)=\{3,5\}, A\left(s_3\right)=\left\{2,3\right\}, and A\left(s_4\right)=\{2,4\}. It is verified that A_i(1\le i\le 4) satisfies Assertion 2.1. Therefore, G has a weakly edge-face 5-coloring.

Case 1.2.1b: \pi \left(f_{y{y}^{\prime }}^o\right)=5 and \pi \left(uy\right)\ne 5.

It is found that \pi \left(uy\right)=3. First, change the color of uv to \alpha \in \mathcal{C}\setminus \{1,2,3,\pi (u{u}^{\prime }\left)\right\}. If α = 5, then A\left(s_1\right)=\{1,4\}, A\left(s_2\right)=\{3,5\}, A\left(s_3\right)=\left\{1,3\right\}, and A\left(s_4\right)=\{4,5\}. A weakly edge-face 5-coloring of G is obtained according to Assertion 3.1. If α = 4, further change the color of yv₂ to 5. Then there are A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\left\{3,4\right\}, A\left(s_3\right)=\left\{1,3\right\}, and A\left(s_4\right)=\{4,5\}, thus getting a weakly edge-face 5-coloring of G.

Case 1.2.1c: \pi \left(f_{y{y}^{\prime }}^o\right)\ne 5 and \pi \left(uy\right)=5.

If \pi \left(u{u}^{\prime }\right)\ne 4, then first change the color of uv to 4, and the subsequent discussion process is similar to the latter subcase of Case 1.2.1b. Now assume \pi \left(u{u}^{\prime }\right)=4. If \pi \left(u{u}^{″}\right)\ne 1, then swap the colors of uv and uy, so that A\left(s_1\right)=\{1,4\}, A\left(s_2\right)=\{3,5\}, A\left(s_3\right)=\left\{1,3\right\}, and A\left(s_4\right)=\{4,5\}. According to Assertion 3.1, a weakly edge-face 5-coloring of G can be obtained. Now assume \pi \left(u{u}^{″}\right)=1. If it is possible to change the color of uy to 2 or 3, then further change the color of f_{y{v}_2}^o to 5, that is, A\left(s_1\right)=\{4,5\}, A\left(s_2\right)=\{3,5\}, A\left(s_3\right)=\left\{2,3\right\}, and A\left(s_4\right)=\{2,4\}. Then, by applying Assertion 3.1, a weakly edge-face 5-coloring of G can be constructed. Otherwise, there must be that \pi \left(y{y}^{\prime }\right)=2 and \pi \left(f_{y{y}^{\prime }}^o\right)=3. At this point, change the colors of both yv₂ and uv to 5 and then change the color of uy to 4. As a result, there are A\left(s_1\right)=\{1,4\}, A\left(s_2\right)=\{3,4\}, A\left(s_3\right)=\left\{1,3,4\right\}, and A\left(s_4\right)=\{4,5\}. Let A^{\prime }\left(s_3\right)=\{1,3\}. It is verified that A(s₁), A(s₂), A^{\prime }(s₃), A(s₄) satisfy Assertion 3.1. Q.E.D.

Case 1.2.2: \pi \left(y{v}_2\right)=\pi \left(f_{x{v}_1}^o\right).

Without losing generality, assume \pi \left(y{v}_2\right)=\pi \left(f_{x{v}_1}^o\right)=2, \pi \left(x{v}_1\right)=3, and \pi \left(f_{y{v}_2}^o\right)=4. At this point, \pi \left(uv\right)\in \{1,5\}. If \pi \left(uv\right)=5, color vv₁ with color 4, v₁v₂ with color 5, vv₂ with color 1, and f_{v_1{v}_2}^o with color 3.

Next, assume \pi \left(uv\right)=1. For m\in \{3,5\}, if m\notin \{\pi \left(y{y}^{\prime }\right),\pi \left(uy\right)\}, then change the color of yv₂ to m. If m = 5, then A\left(s_1\right)=\{4,5\}, A\left(s_2\right)=\{2,4\}, A\left(s_3\right)=\{2,3\} and A\left(s_4\right)=\{3,5\}. If m = 3, then A\left(s_1\right)=\left\{4,5\right\}, A\left(s_2\right)=\{2,4,5\}, A\left(s_3\right)=\left\{2,5\right\}, and A\left(s_4\right)=\{3,5\}. It is verified that in these two cases, there is always A_i that satisfies the conditions of Assertion 3.1 and thus constructs a weakly edge-face 5-coloring of G. Now assume \{\pi \left(y{y}^{\prime }\right),\pi \left(uy\right)\}=\{3,5\}. First, consider the case wherein \pi \left(y{y}^{\prime }\right)=3 and \pi \left(uy\right)=5. First change the color of uv to \alpha \in \{3,4\}\mathrm{\setminus }\left\{\pi \left(u{u}^{\prime }\right)\right\}. If α = 3, then A\left(s_1\right)=\left\{1,4,5\right\},A\left(s_2\right)=\left\{4,5\right\},A\left(s_3\right)=\left\{1,5\right\}, and A\left(s_4\right)=\{3,5\}. If α = 4, then further change the color of f_{y{v}_2}^o to 3 and the color of yv₂ to 4. At this time, A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\left\{2,5\right\},A\left(s_3\right)=\left\{1,2,5\right\}, and A\left(s_4\right)=\{4,5\}. In both cases, there is available color set that meets the conditions of Assertion 3.1 so that G has a weakly edge-face 5-coloring. Now consider the case wherein \pi \left(y{y}^{\prime }\right)=5 and \pi \left(uy\right)=3. Similarly, change the color of uv to {\alpha }^{\prime }\in \{4,5\}\mathrm{\setminus }\left\{\pi \left(u{u}^{\prime }\right)\right\}. If {\alpha }^{\mathrm{\prime }} = 5, there are A\left(s_1\right)=\left\{1,4\right\},A\left(s_2\right)=\{4,5\}, A\left(s_3\right)=\left\{1,3\right\}, and A\left(s_4\right)=\{3,5\}. If \text{alpha^'=4}, then further change the color of f_{y{v}_2}^o to 5, and then we can deduce that A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\{4,5\}, A\left(s_3\right)=\left\{1,3\right\}, and A\left(s_4\right)=\{3,4\}. According to Assertion 3.1, construct a weakly edge-face 5-coloring of G.

Case 1.3: \left|\pi \left(\mathcal{A}\right)\right|=2.

Without losing generality, assume \pi \left(x{v}_1\right)=\pi \left(f_{y{v}_2}^o\right)=2 and \pi \left(y{v}_2\right)=\pi \left(f_{x{v}_1}^o\right)=3. It is found that \pi \left(uv\right)\in \{1,4,5\}.

Case 1.3a: \pi \left(uv\right)=1.

It is found \pi \left(uy\right)\in \{4,5\}. Without losing generality, assume \pi \left(uy\right)=4. Then \pi \left(f_{y{y}^{\prime }}^o\right)\in \{3,5\}. If \pi \left(f_{y{y}^{\prime }}^o\right)=3, then first change the color of f_{y{v}_2}^o to 5 and then go back to Case 1.2.2. If \pi \left(f_{y{y}^{\prime }}^o\right)=5, then \pi \left(y{y}^{\prime }\right)=2. Change the color of yv₂ to 5 and then return to Case 1.2.1.

Case 1.3b: \pi \left(uv\right)\in \{4,5\}.

Without losing generality, assume \pi \left(uv\right)=4. If \pi \left(uy\right)\ne 5 and \pi \left(f_{y{y}^{\prime }}^o\right)\ne 5, then first change the color of f_{y{v}_2}^o to 5, then there are A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\{4,5\}, A\left(s_3\right)=\left\{1,2\right\}, and A\left(s_4\right)=\{2,4\}. According to Assertion 3.1, construct a weakly edge-face 5-coloring of G. Now assume \pi \left(f_{y{y}^{\prime }}^o\right)=5 or \pi \left(uy\right)=5. If \pi \left(f_{y{y}^{\prime }}^o\right)=5, then first change the color of yv₂ to 5, and there are A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\{3,4\}, A\left(s_3\right)=\left\{1,3\right\}, and A\left(s_4\right)=\{4,5\} and thus obtain a weakly edge-face 5-coloring of G according to Assertion 3.1. Now assume that \pi \left(uy\right)=5. If \pi \left(y{y}^{\prime }\right)=4, then there must be \pi \left(f_{y{y}^{\prime }}^o\right)=3. First, change the color of f_{y{v}_2}^o to 5, and then color uy with a color different from 3, 4, 5, π(u{u}^{″}). Consequently, there are A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\{4,5\}, A\left(s_3\right)=\left\{1,2\right\}, and A\left(s_4\right)=\{2,4\}. If \pi \left(y{y}^{\prime }\right)\ne 4, then the color of y{y}^{\prime } can only be 2. First, change the color of yv₂ to 4 and then obtain A\left(s_1\right)=\{1,5\}, A\left(s_2\right)=\{3,5\}, A\left(s_3\right)=\left\{1,3,5\right\}, and A\left(s_4\right)=\{4,5\}. It is verified that in these two cases there is always A_i that satisfies the conditions of Assertion 3.1 and then construct a weakly edge-face 5-coloring of G.

Case 2: G contains the structure (A2).

Let G^{\ast }=G-\{v_1,v_2,w_1,w_2\}+\{vx,vw,yw\}. G* is a Halin graph, \mathrm{\Delta }\left(G^{\ast }\right)=\mathrm{\Delta }\left(G\right) and \left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G^{\ast }\right)\right|=\left|V_{\mathrm{i}\mathrm{n}\mathrm{t}}\left(G\right)\right|-2=k-1. By the induction hypothesis, G* has a weakly edge-face 5-coloring π*. Similarly, denote the outer face of G* as f* and the face incident to f* at the edge e as f_e^{\ast }. Without losing generality, assume {\pi }^{\ast }\left(f^{\ast }\right)=1. Similarly, extend π* to G such that G has a weakly edge-face 5-coloring π. Denote \mathcal{B}=\{x{v}_1,f_{x{v}_1}^o,y{w}_2,f_{y{w}_2}^o\} and {\mathcal{S}}^{\prime }=\{v{v}_1,v_1{v}_2,v{v}_2,f_{v_1{v}_2}^o,v_2{w}_1,f_{v_2{w}_1}^o,w{w}_1,w_1{w}_2,w{w}_2,f_{w_1{w}_2}^o\}.

Firstly, let \pi \left(f^o\right)=1. Secondly, assign the colors xv,f_{xv}^{\ast },yw,f_{yw}^{\ast } in G* to the corresponding elements x{v}_1,f_{x{v}_1}^o,y{w}_2,f_{y{w}_2}^o in G. After that, let \pi \left(s\right)={\pi }^{\ast }\left(s\right), where s\in E\left(G\right)\cup F\left(G\right)\mathrm{\setminus }\left(\mathcal{B}\cup {\mathcal{S}}^{\prime }\cup \left\{f^o\right\}\right). Next, it requires to show that the elements in {\mathcal{S}}^{\prime } can also be properly colored so that G is weakly edge-face 5-colorable. Denote \mathcal{M}=\{uv,vw,uw,f_{vw}^{\ast }\} again and use {\pi }^{\ast }\left(\mathcal{M}\right) to represent the set of colors of all elements in \mathcal{M} at G*. Obviously, \left|{\pi }^{\ast }\left(\mathcal{M}\right)\right|=4. The two cases will be discussed following according to the occurrence of color 1.

Case 2.1: 1\notin {\pi }^{\ast }\left(\mathcal{M}\right).

At this time, {\pi }^{\ast }\left(\mathcal{M}\right)=\{2,3,4,5\}. Without losing generality, assume {\pi }^{\ast }\left(uv\right)=2, {\pi }^{\ast }\left(vw\right)=3, {\pi }^{\ast }\left(uw\right)=4, and {\pi }^{\ast }\left(f_{vw}^{\ast }\right)=5. Firstly, assign the color \pi \left(f_{x{v}_1}^o\right) to v₁v₂ and the color \pi \left(f_{y{w}_2}^o\right) to w₁w₂. Secondly, color both vv₂ and ww₁ with color 1, color f_{v_1{v}_2}^o with color 2, color f_{w_1{w}_2}^o with color 4, and color f_{v_2{w}_1}^o with color 5. Finally, color vv₁ with \alpha \in \mathcal{C}\mathrm{\setminus }\{1,2,\pi \left(x{v}_1\right),\pi \left(f_{x{v}_1}^o\right)\}, color ww₂ with \beta \in \mathcal{C}\mathrm{\setminus }\{1,4,\pi \left(y{w}_2\right),\pi \left(f_{y{w}_2}^o\right)\}, and color v₂w₁ with \gamma \in \mathcal{C}\mathrm{\setminus }\{1,5,\pi \left(f_{x{v}_1}^o\right),\pi \left(f_{y{w}_2}^o\right)\}.

Case 2.2: 1\in {\pi }^{\ast }\left(\mathcal{M}\right).

By symmetry, without losing generality, assume {\pi }^{\ast }\left(uv\right)=1, {\pi }^{\ast }\left(vw\right)=2, {\pi }^{\ast }\left(uw\right)=3, and {\pi }^{\ast }\left(f_{vw}^{\ast }\right)=4. For the convenience, denote \pi \left(x{v}_1\right)=\alpha, \pi \left(f_{x{v}_1}^o\right)=\beta, \pi \left(y{w}_2\right)=\gamma , and \pi \left(f_{y{w}_2}^o\right)=\eta. It is noted that \alpha \ne \beta and \gamma \ne \eta. According to the occurrence of color 5, there are the following two cases.

(i) 5\notin \{\gamma ,\eta \}. This implies that γ = 4 and η = 2. First, assume 5\notin \{\alpha ,\beta \}. Then \alpha \in \{3,4\} and \beta \in \{2,3\}. Color v_1{v}_2,w{w}_2,f_{v_2{w}_1}^o with color 5, f_{v_1{v}_2}^o with color α, vv₂ with color β, ww₁ with color 1, w₁w₂ with color 2, and f_{w_1{w}_2}^o with color 4. Then, since \left|C\right|=5, there are always colors being assigned to vv₁ and v₂w₁ respectively, such that G is weakly edge-face 5-colorable.

Now assume 5\in \{\alpha ,\beta \}. First, consider the case wherein \alpha =5. Color ww₁ with color 1, w₁w₂ with color 2, and f_{w_1{w}_2}^o with color 3. Color v_1{v}_2,f_{v_2{w}_1}^o with color 4 simultaneously, color v_2{w}_1,w{w}_2,f_{v_1{v}_2}^o with color 5 simultaneously, and color vv₂with color β. Finally, color vv₁ with a color different from 1 ,4, 5, β.

Now consider the case wherein β = 5. It is noted that \alpha \in \{3,4\}.

If α = 3, then color ww₂ with color 1, vv₂, ww₁ with color 2, color v_2{w}_1,f_{v_1{v}_2}^o,f_{w_1{w}_2}^o with color 3, color v{v}_1,f_{v_2{w}_1}^o with color 4, and color v₁v₂, w₁w₂ with color 5.

If α = 4, first denote u{u}^{″} as the edge adjacent to the face uw and incident to f_{w_{2}y}^o. Then change the color of uw to a\in \mathcal{C}\setminus \{1,2,3,\pi (u{u}^{″}\left)\right\}. Next, color ww₂ with color 1, vv₁, v₂w₁ with color 2, color v_1{v}_2,w_1{w}_2,f_{v_2{w}_1}^o with color 3, color f_{v_1{v}_2}^o with color 4, and color vv₂ with color 5. Finally, color f_{w_1{w}_2}^o with color a and color ww₁ with b\in \{4,5\}\mathrm{\setminus }\left\{a\right\}.

(ii) 5\in \{\gamma ,\eta \}. First, assume γ = 5. Then there must be η = 2. If 5\notin \{\alpha ,\beta \}, then color ww₁ with color 1, w₁w₂ with color 2, f_{w_1{w}_2}^o with color 3, v₂w₁, ww₂ with color 4, and v_1{v}_2,f_{v_2{w}_1}^o with color 5. Then color f_{v_1{v}_2}^o with color α, and vv₂ with color β. Finally, color vv₁ with a color different from 1, 5, α, β. Now assume 5\in \{\alpha ,\beta \}.

(1) Suppose α = 5. Then \beta \in \{2,3\}. We color ww₁ with color 1, w₁w₂ with color 2, f_{w_1{w}_2}^o with color 3, vv₁, ww₂, f_{v_2{w}_1}^o with color 4, and v_2{w}_1,f_{v_1{v}_2}^o with color 5. Then color v₁v₂ with color β. Finally, color vv₂ with a color different from 1, 4, 5, β.

(2) Suppose β = 5. Then \alpha \in \{3,4\}. If α = 3, similarly color ww₁ with color 1, vv₁, w₁w₂ with color 2, v₂w₁, f_{v_1{v}_2}^o,f_{w_1{w}_2}^o with color 3, v_1{v}_2,w{w}_2,f_{v_2{w}_1}^o with color 4, and finally color vv₂ with color 5. If α = 4, denote u{u}^{″} as the edge adjacent to face uw and incident to f_{w_{2}y}^o. First, color uw with a color different from 1, 2, 3, π(u{u}^{″}). Then color ww₁ with color 1, vv₁, w₁w₂ with color 2, w{w}_2,v_1{v}_2,f_{v_2{w}_1}^o with color 3, f_{v_1{v}_2}^o,v_2{w}_1 with color 4, and f_{w_1{w}_2}^o,v{v}_2 with color 5.

Now assume η = 5. Then there must be γ = 4.

(1) If 5\notin \{\alpha ,\beta \}, then first color v₁v₂ with color 5, f_{v_1{v}_2}^o with color α, and vv₂ with color β. Then color vv₁ with a color different from 1, 5, α, β. If there exists a color a\in \mathcal{C}\mathrm{\setminus }\{1,3,5,\alpha ,\beta \}, then color f_{v_2{w}_1}^o with color a, and v₂w₁ with color b\in \mathcal{C}\mathrm{\setminus }\{1,5,a,\beta \}. It is found that a\in \{2,4\} and b\in \{2,3,4\}. Thus, a weakly edge-face 5-coloring of G can be obtained by coloring ww with color 1, w{w}_2with color 2, f_{w_1{w}_2}^o with color 3, and w₁w₂ with color 5. Now assume that such a color a does not exist. Then there is only one possibility: that is, α = 4 and β = 2. At this time, first color ww₁ with color 1, w₁w₂ with color 2, ww₂, f_{v_2{w}_1}^o simultaneously with color 3, vw₁, f_{w_1{w}_2}^o simultaneously with color 4, and then change the color of uw to a color different from 1, 3, 5, π(u{u}^{″}), where u{u}^{″} is the edge adjacent to the face uw and incident to f_{y{w}_2}^o.

(2) Now assume 5\in \{\alpha ,\beta \}. If β = 5, then first assign the color α to f_{v_1{v}_2}^o. Then color ww₁ with color 1, vv₁, ww₂, f_{v_2{w}_1}^o with color 2, f_{w_1{w}_2}^o with color 4, and vv₂,w₁w₂ with color 5. Finally, color v₁v₂ with a\in \mathcal{C}\mathrm{\setminus }\{1,2,5,\alpha \}, and then color v₂w₁ with b\in \mathcal{C}\mathrm{\setminus }\{1,2,5,a\}. Next, consider the case wherein α = 5. If β = 3, color ww₁ with color 1, vv₁, ww₂, f_{v_2{w}_1}^o with color 2, vv₂, f_{w_1{w}_2}^o with color 3, v₂w₁, f_{v_1{v}_2}^o with color 4, and v₁v₂,w₁w₂ with color 5. If β = 2, color ww₁ with color 1, vv₂,ww₂ with color 2, vv₁ ,v₂w₁, f_{w_1{w}_2}^o with color 3, v₁v₂, f_{v_2{w}_1}^o with color 4, and w₁w₂, f_{v_1{v}_2}^o with color 5.

Case 3: G contains the structure (A3).

Let G^{\ast }=G-\{v_1,v_2,\dots ,v_t\}+\{vx,vy\}. G* is a Halin graph, \mathrm{\Delta }\left(G^{\ast }\right)=\mathrm{\Delta }\left(G\right) and . By the induction hypothesis, G* has a weakly edge-face 5-coloring π*. Similarly, denote the outer face of G* as f*, and the face incident to f* at the edge e as f_e^{\ast }. Next, extend π* to G such that G has a weakly edge-face 5-coloring π. Without losing generality, assume {\pi }^{\ast }\left(f^{\ast }\right)=1. Denote D=\{x{v}_1,f_{x{v}_1}^o,y{v}_t,f_{y{v}_t}^o\} and \{v{v}_1,v{v}_2,\dots ,v{v}_t,v_1{v}_2,v_2{v}_3,\dots ,v_{t-1}{v}_t,f_{v_1{v}_2}^o,f_{v_2{v}_3}^o,\dots ,f_{v_{t-1}{v}_t}^o\}.

Firstly, let \pi \left(f^o\right)=1. Secondly, assign the colors of xv,f_{x}v,f_{xv}^{\ast },yv,f_{yv}^{\ast } in G* to the corresponding elements x{v}_1,f_{x{v}_1}^o,y{v}_t,f_{y{v}_t}^o in G. Then, let \pi \left(s\right)={\pi }^{\ast }\left(s\right), where s\in E\left(G\right)\cup F\left(G\right)\mathrm{\setminus }\left(\mathcal{D}\cup {\mathcal{S}}^{″}\cup \left\{f^o\right\}\right). It requires to prove that the elements in {\mathcal{S}}^{″} can also be colored properly so that G is weakly edge-face 5-colorable. Denote \pi \left(D\right) as the color set for all elements in \mathcal{D} at G. It is found that 2\le \left|\pi \left(D\right)\right|\le 4 and 1\notin \pi \left(D\right). The following will discuss the three cases.

Case 3.1: \left|\pi \left(\mathcal{D}\right)\right|=4.

Without losing generality, assume \pi \left(x{v}_1\right)=2, \pi \left(f_{x{v}_1}^o\right)=3, \pi \left(y{v}_t\right)=4, and \pi \left(f_{y{v}_t}^o\right)=5. This indicates that \pi \left(vu\right)=1. If t = 3, color vv₃, f_{v_1{v}_2}^o with color 2, vv₂ with color 3, v₁v₂, f_{v_2{v}_3}^o with color 4, and color vv₁, v₂v₃ with color 5. It is verified that the resulting coloring is a weakly edge-face 5-coloring of G. Now assume t ≥ 4. First, color vv_t, f_{v_1{v}_2}^o with color 2, v₁v₂ with color 3, vv₁, f_{v_{t-1}{v}_t}^o with color 4, and v_{t-1}{v}_t, f_{v_{t-2}{v}_{t-1}}^o with color 5. Then, when t is odd, color v{v}_{t-1} with color 1; otherwise, color v{v}_{t-1} with color 3. Next, color the uncolored edges and faces in {\mathcal{S}}^{″} to obtain a weakly edge-face 5-coloring of G. For the edges, let 2\le i\le t-2. If i is even, color the edges vv_i and v_i{v}_{i+1} with colors 1 and 4 respectively. If i is odd, color the edges vv_i and v_i{v}_{i+1} with colors 2 and 3 respectively. For the faces, let 2\le j\le t-3. If j is even, color the face f_{v_j{v}_{j+1}}^o with color 3. If j is odd, color the face f_{v_j{v}_{j+1}}^o with color 4.

Case 3.2: \left|\pi \left(\mathcal{D}\right)\right|=3.

Without losing generality, assume \pi \left(x{v}_1\right)=\pi \left(f_{y{v}_t}^o\right)=2, \pi \left(f_{x{v}_1}^o\right)=3, and \pi \left(y{v}_t\right)=4. It is found that \pi \left(uv\right)\in \{1,5\}. Firstly, color f_{v_{t-1}{v}_t}^o with color 4. Secondly, color v{v}_{t-1} with the same color as uv, and color vv_t with a\in \{1,5\}\mathrm{\setminus }\left\{\pi \left(uv\right)\right\}. Next, let 1\le i\le t-1. If i is even, color the edge v_i{v}_{i+1} with color 2. If i is odd, color the edge v_i{v}_{i+1} with color 3. Then, let 1\le j\le t-2. If j is odd, color the edge vv_j with color a and the face f_{v_j{v}_{j+1}}^o with color 2. If j is even, color the edge vv_j with color 4 and the face f_{v_j{v}_{j+1}}^o with color 3.

Case 3.3: \left|\pi \left(\mathcal{D}\right)\right|=2.

Without losing generality, assume \pi \left(x{v}_1\right)=\pi \left(f_{y{\upsilon }_t}^o\right)=2 and \pi \left(y{v}_t\right)=\pi \left(f_{x{\upsilon }_1}^o\right)=3. It is known that \pi \left(uv\right)\in \{1,4,5\}. Now, extend {\pi }^{\ast } to G in different cases according to the value of t to complete the proof of Theorem 1.2.

(1) t = 3. First, color f_{v_2{v}_3}^o with color 3. Then color v₂v₃ and f_{v_1{v}_2}^o with color 4. After that, color vv₁ and vv₃ with b\in \{1,5\}\mathrm{\setminus }\left\{\pi \left(uv\right)\right\}. Finally, color v₁v₂ with color 3 and vv₂ with color 2.

(2) t ≥ 4. First, color f_{v_{t-1}{v}_t}^o with color 3 and v{v}_{t-1} with \pi \left(uv\right). Then color v_{t-1}{v}_t, f_{v_{t-2}{v}_{t-1}} with a\in \{4,5\}\mathrm{\setminus }\left\{\pi \left(uv\right)\right\}. Next, color v{v}_{t-2}, vv_t with b\in \{1,4,5\}\mathrm{\setminus }\{a,\pi \left(uv\right)\}. Now, let 1\le i\le t-2. If i is odd, color the edge v_i{v}_{i+1} with color 3. If i is even, color the edge v_i{v}_{i+1} with color 2. Then, let 1\le j\le t-3. If j is odd, color the edge vv_j with color a and the face f_{v_j{v}_{j+1}}^o with color 2. If j is even, color the edge vv_j with color π(uv) and the face f_{v_j{v}_{j+1}}^o with color 3.

References

[1] BondyJ.A. , Murty, U.S.R., Graph Theory, London: Springer-Verlag, 2008

[2] Chen M., Raspaud, A. , Wang, W.F. . Plane graphs with maximum degree 6 are edge-face 8-colorable. Graphs Combin. 2014; 30: 861–874

[3] Chen M. , Wang, W.F. . The 2-dipath chromatic number of Halin graphs. Inform. Process. Lett. 2006; 99: 47–53

[4] Fabrici I., Jendrol, S. , Vrbjarová, M. . Facial entire colouring of plane graphs. Discrete Math. 2016; 339: 626–631

[5] Fiamčík . Simultaneous coloring of 4-valent maps. Math. Slovaca 1971; 21: 9–13

[6] Gong Q.Y. , Wu, J.L. . Edge-face coloring of Halin graphs. Inform. Tech. 2008; 7: 64–67

[7] Jucovič . On a problem in map coloring. Math. Slovaca 1969; 19: 225–227

[8] MelnikovL.S., Problem 9, In: Recent Advances in Graph Theory (Fiedler, M. ed.), Proceedings of the Second Czechoslovak Symposium, Prague, June, 1974, Academia Prague, Czechoslovak, 1975, p. 543

[9] Sanders D.P. , Zhao, Y. . On simultaneous edge-face colorings of plane graphs. Combinatorica 1997; 17: 441–445

[10] Sanders D.P. , Zhao, Y. . A five-color theorem. Discrete Math. 2000; 220: 279–281

[11] Sanders D.P. , Zhao, Y. . On improving the edge-face coloring theorem. Graphs Combin. 2001; 17: 329341

[12] Sereni J. , Stehlik, M. . Edge-face colouring of plane graphs with maximum degree nine. J. Graph Theory 2011; 66: 332–346

[13] Waller A.O. . Simultaneous colouring the edges and faces of plane graphs. J. Combin. Theory Ser. B 1997; 69: 219–221

[14] Wang W.F. , Lih, K. . A new proof of Melnikov’s conjecture on the edge-face coloring of plane graphs. Discrete Math. 2002; 253: 87–95

RIGHTS & PERMISSIONS

Higher Education Press 2025