On the Equitable Edge-Coloring of 1-Planar Graphs and Planar Graphs

Abstract

An edge-coloring of a graph G is equitable if, for each vertex v of G, the number of edges of any one color incident with v differs from the number of edges of any other color incident with v by at most one. In the paper, we prove that every 1-planar graph has an equitable edge-coloring with k colors for any integer $k\ge 21$, and every planar graph has an equitable edge-coloring with k colors for any integer $k\ge 12$.

1 Introduction

Throughout the paper, all graphs are finite, simple and undirected. Let G be a graph. Denote by V(G) and E(G) the set of vertices and the set of edges of G, respectively. Let $N_G(v)$ denote the set of vertices adjacent to a vertex v, and $d_{G}(x)=|N_G(v)|$, or simply d(x), denote the degree of a vertex x in G. We use $\delta (G)$ and $\Delta (G)$ to denote the minimum degree and the maximum degree of G, respectively. An odd cycle is a cycle in which the number of edges is odd.

A k-edge-coloring of G is an assignment of colors to the edges of G with k colors $1,2,\ldots ,k$. Let $\varphi$ be a k-edge-coloring of G. For each vertex $v\in V(G)$, let $c_i(\varphi ,v)= |\{uv\in E(G)\,|\,\varphi (uv)=i\}|$ and $C_\varphi (v)= \{i\,|\,c_i(\varphi ,v)=\min \nolimits _{1\le j\le k}c_j(\varphi ,v)\}$, thus $|C_\varphi (v)|\ge 1$. A k-edge-coloring $\varphi$ is equitable if for each $v \in V(G)$, we have

$$\begin{aligned} |c_i(\varphi , v)-c_j(\varphi , v)| \le 1 \quad (1 \le i<j \le k). \end{aligned}$$

A graph G is equitable k-edge-colorable if G has an equitable edge-coloring with k colors. The equitable chromatic index $\chi '_{=}(G)$ of a graph G is the smallest number k such that G has an equitable k-edge-coloring. However, an equitable k-edge-colorable graph may admits no equitable $k'$-edge-colorings for some $k'>k$. An odd cycle is is equitable 1-colorable but not equitable 2-colorable. The equitable edge chromatic threshold $\chi '_{\equiv }(G)$ of G is the smallest k such that G has equitable edge colorings for any number of colors greater than or equal to k. A graph G is equitable if $\chi '_{\equiv }(G)=1$. A circuit is a connected graph in which each vertex has even degree. A circuit is odd (or even) if the number of edges is odd (or even, respectively). It is stated in [8] that a connected graph G has an equitable 2-edge-coloring if and only if it is not an odd circuit. This implies that all bipartite graphs are equitable. Wu [9] proved that a connected outerplanar graph is equitable if and only if it is not an odd circuit. Song, Wu and Liu [7] extended the result to series-parallel graphs. Hilton and Werra [3] proved that if k does not divide d(v) for all vertex $v \in V(G)$, then G has an equitable k-edge-coloring, and an extended result can be seen in [11].

In this paper, we consider the equitable edge coloring of planar graphs and 1-planar graphs, and obtain that $\chi '_{\equiv }(G)\le 21$ if G is a 1-planar graph, and $\chi '_{\equiv }(G)\le 12$ if G is a planar graph. In the following, we always assume that all planar graphs have been embedded on the plane such that edges meet only at points corresponding to their common ends, and all 1-planar graphs have been embedded on the plane such that every edge is crossed by at most one other edge and the number of crossings is as small as possible. This notion of 1-planar graphs is introduced by Ringel [5] while trying to simultaneously color the vertices and faces of a planar graph such that any pair of adjacent or incident elements receive different colors.

For convenience, we introduce some more notations and definitions. Let G be a planar graph. For a face f of G, the degree d(f) of f is the number of edges incident with f, where each cut-edge is counted twice. A vertex (face) x is called a k-vertex (k-face), $k^{+}$-vertex ($k^{+}$-face) and $k^{-}$-vertex, if $d(x)=k$, $d(x)\ge k$ and $d(x)\le k$, respectively. Let $\delta (f)$ denote the minimum degree of vertices incident with the face f. We use $m_{i}(v)$ to denote the number of i-faces incident with v for each $v\in V(G)$ and each positive integer $i\ge 3$. We use $(d_{1},d_{2},\ldots ,d_{n})$ to denote a face f if $(d_{1},d_{2},\ldots ,d_{n})$ are the degree of vertices incident to the face f. If $(u_{1},u_{2},\ldots ,u_{n})$ are the vertices on the boundary walk of a face f, then we write $f=u_{1}u_{2}\cdots u_{n}$.

2 1-Planar Graphs

Firstly, let us describe a result proved by Borodin et al. [1]. A k-edge coloring is called proper if every two adjacent edges receive different colors. We say that L is an edge assignment for the graph G if it assigns a list L(e) of possible colors to each edge e of G. If G has a proper edge-coloring $\varphi$ such that $\varphi (e)\in L(e)$ for each edge e of G, then we say that G is edge-L-colorable or $\varphi$ is an edge-L-coloring of G. A graph G is said to be edge f-choosable if, whenever we give a list L(e) of f(e) colors to each edge e of G, G is edge-L-colorable. If $f(e)\equiv k$ for each edge $e\in E(G)$, then G is said to be edge k -choosable.

Lemma 1

[1] A bipartite graph G is edge f-choosable where $f(e)=\max \{d(u),d(v)\}$ for $e=uv\in E(G)$.

The associated plane graph $G^{\times }$ of a 1-planar graph G is the planar graph that is obtained from G by turning all crossings of G into new 4-vertices. We call the new vertices in $G^{\times }$ crossing vertices. For a vertex $v\in V(G^{\times })$, we use $f_k(v)$ to denote the number of k-faces which is incident with it and $n_c(v)$ to denote the number of crossing vertices adjacent to v.

Lemma 2

[13] If G is a 1-planar graph, then the following results hold.

• (a) For any two crossing vertices u and v in $G^{\times }$, $uv\not \in E(G^{\times })$.

• (b) If there is a 3-face uvwu in $V(G^{\times })$ such that $d_{G^{\times }}(v)=2$, then u and w are not crossing vertices.

• (c) If a 3-vertex v in $V(G^{\times })$ is incident with two 3-faces and adjacent to two crossing vertices, then v must also be incident with a face of degree $\ge 5$.

• (d) There exists no edge uv such that $d_{G^{\times }}(u)=3$, v is the crossing vertex, and uv is incident with two 3-faces.

Lemma 3

[12]

$$\begin{aligned} f_3(v)+n_c(v)\le \left\{ \begin{array}{ll} 3, &{} \quad \hbox {if } \; d(v)=3 \quad \hbox { and } \quad f_3(v)\ne 2; \\ 4, &{} \quad \hbox {if } \; d(v)=3 \quad \hbox { and } \quad f_3(v)=2; \\ 5, &{} \quad \hbox {if } \; d(v)=4; \\ \left\lfloor \frac{3d(v)}{2}\right\rfloor , &{} \quad \hbox {if } \; d(v)\ge 5. \end{array} \right. \end{aligned}$$

A 3-face of $G^{\times }$ is of type one if it is incident with one crossing vertex, one $7^-$-vertex and one $8^+$-vertex, and is of type two otherwise. Note that if f is a type two 3-face, then f shall be incident with at least two $8^+$-vertices because any two $7^-$-vertices are not adjacent by Lemma 6 and any two crossing vertices are not adjacent by the 1-planarity of G.

Lemma 4

[12] Each $8^+$-vertex v in $G^{\times }$ is incident with at most $\lceil \frac{f_3(v)}{2}\rceil +1$ type one 3-faces if $f_3(v)=d(v)-2$, at most $\lceil \frac{f_3(v)}{2}\rceil$ type one 3-faces if $f_3(v)=d(v)-1$ and at most $\lfloor \frac{f_3(v)}{2}\rfloor$ type one 3-faces if $f_3(v)=d(v)$.

Theorem 1

If G is a 1-planar graph, then $\chi '_{\equiv }(G)\le 21$.

Proof

The proof is carried out by contradiction. Let G be a minimal counterexample to the theorem in terms of the number of vertices and edges, that is, there is an integer $k(\ge 21)$ and a graph G such that G is not equitable k-edge-colorable, but all subgraph of G is equitable k-edge-colorable. Let $C=\{1,2,\ldots , k\}$ be the color set. It is obvious that G is connected. We first prove some lemmas.

Lemma 5

$\delta (G)\ge 2$.

Proof

Suppose that G has an edge uv with $d_G(u)=1$. Then $G'=G-uv$ has an equitable edge-coloring $\varphi$ with k colors by the minimality of G. We draw uv with a color in $C_\varphi (v)$ to extend $\varphi$ to an equitable edge-coloring with k colors, a contradiction. $\square$

Lemma 6

For any $uv\in E(G)$, $d_G(u)+d_G(v)\ge 23$.

Proof

Suppose that G has an edge uv with $2\le d_G(u)\le d_G(v)$ and $d_G(u)+ d_G(v) \le 22$. Then $G'=G-uv$ has an equitable k-edge-coloring $\varphi$ by the minimality of G. Since $d_G(u)+ d_G(v) \le 22$, $d_{G'}(v)=d_G(v)-1\le 19$, each color is appeared at u and v at most once. So we can choose a color in $C\backslash (C_\varphi (u) \cup C_\varphi (v))$ to color uv to extend $\varphi$ to an equitable k-edge-coloring of G, a contradiction. $\square$

Lemma 7

For some $i(2\le i\le 5)$, let $X_i=\{x \in V(G) ~|~ d_G(x)\le i\}$ and $Y_i= \cup _{x \in X_i}N(x)$. If $X_i\ne \emptyset$, then there exists a bipartite subgraph $M_i$ of G with partite sets $X_i$ and $Y_i$ such that $d_{M_i}(x)=1$ for any $x \in X_i$ and $d_{M_i}(y) \le i-1$ for any $y \in Y_i$. Here, we call w the i-master of u if $uw\in M_i$ and $u\in X_i$.

Proof

Without loss of generality, we denote that $X=X_i$, $Y=Y_i$ and $M=M_i$. By Lemmas 5 and 6, X is an independent set of vertices. Let $G'$ be the bipartite subgraph induced by X and Y, and H a maximum bipartite subgraph with partite sets a subset $X'$ of X and Y such that $d_{H}(x) = 1$ for any $x \in X'$ and $d_{H}(y) \le i-1$ for any $y \in Y$. Since there is at least one edge from X to Y, H is not empty. Note that there may be some isolated vertices in Y of H.

Suppose, to the contrary, that $X' \ne X$, that is, there exists a vertex $v \in X \backslash X'$. An $alternating\,\,path$, $P_v$, is a path whose origin is v and the edges are alternating between $E(G') {\setminus } E(H)$ and E(H). If there exists an alternating path $P_v=vv_1v_2\cdots v_{2m+1}$ such that $d_{H}(v_{2m+1})<i-1$, then $H^*=(H - \{v_1v_2,v_3v_4,\ldots , v_{2m-1}v_{2m} \}) + \{vv_1, v_2v_3, \ldots , v_{2m}v_{2m+1}\}$ is a bigger bipartite subgraph than H, a contradiction to the maximality of H. So for every alternating path $P_v$ which terminates at a vertex $v'\in Y$, we have $d_{H}(v')=i-1$.

Let Z denote the set of all vertices connected to v by alternating paths. Let $X''= Z\cap X=\{v\}\cup (Z\cap X')$ and $Y' = Z \cap Y$. It is easy to check that $\cup _{x \in X''} N(x)=Y'$. Let $H'$ be the induced bipartite graph with bipartition $(X'', Y')$. Note that $d_{H'}(x)=d_G(x) \le i$ for each $x \in X''$. Let $y \in Y'$. Since there is at least one alternating path terminated at y, there exists an edge $x'y\in E(H')\backslash E(H)$ and it follows from $d_{H}(y)=i-1$ that $d_{H'}(y) \ge i$. So $d_{H'}(y) \ge i$ for each $y \in Y'$.

By the minimality of G, $G'=G-X''$ has an equitable k-edge-coloring $\varphi$. In the following, we will color edges of $H'$ equitably. For every $y \in Y'$ satisfying $d_{H'}(y) =d>k$, let $d=ak+b(a\ge 1, 0\le b<k)$, we split y into $a+1$ vertices $y_1, y_2,\ldots , y_{a+1}$ of degree $s, t, k, k, \ldots , k$, respectively, such that $i\le s\le k, i\le t\le k$ and $s+t=k+b$. We call $y_i$ the ith splitting vertices of $y(1\le i\le a+1)$ and the new bipartite graph obtained by the splitting operation is denoted by $F=(X'', Y'')$. Then $d_{F}(x)=d_G(x) \le i$ for each $x \in X$ and $i\le d_{F}(y) \le k$ for each $y \in F$. We define the list L(uv) of the edge uv of F, $u\in X'', v\in Y''$ as follows.

• Suppose that $d_{F}(v)=d_{H'}(v)$. Then $d_{F}(v)\le k$. First, we put all colors of $C_{\varphi }(v)$ into L(uv). Then, if $d_{F}(v)=t>|C_{\varphi }(v)|$, then we choose $t-|C_{\varphi }(v)|$ colors from $C\backslash C_{\varphi }(v)$ to put into L(uv);

• Suppose that v is the first splitting vertex of some vertex y of Y. If $d_{F}(v)\le |C_{\varphi }(y)|$, then we choose $d_{F}(v)$ colors from $C_{\varphi }(y)$ to put into L(uv). Otherwise, we first put all colors of $C_{\varphi }(y)$ into L(uv) and then we choose $d_{F}(v)-|C_{\varphi }(y)|$ colors from $C\backslash C_{\varphi }(y)$ to put into L(uv);

• Suppose that v is the second splitting vertex of some vertex y of Y. Let $v'$ be the first splitting vertex of y and $u'\in N_{F}(v')$. First, we put all colors of $C\backslash L(u'v')$ into L(uv). Then, if $d_{F}(v)+d_{F}(v')\le k+|C_{\varphi }(y)|$, then we choose $d_{F}(v)+d_{F}(v')- k$ colors from $C_{\varphi }(y)\cap L(u'v')$ to put into L(uv). Otherwise, we put first all colors of $C_{\varphi }(y)$ into L(uv) and then we choose $d_{F}(v)+d_{F}(v')-k-|C_{\varphi }(y)|$ colors from $L(u'v')\backslash C_{\varphi }(y)$ to put into L(uv);

• Suppose that v is the ith splitting vertex of some vertex y of Y with any $i>2$. Therefore $d_{F}(v)=k$ and we define $L(uv)= C$.

It is obvious that $|L(uv)|\ge \max \{d_{F}(v), d_{F}(u)\}$ for any uv of F where $u\in X, y\in Y'$. By Lemma 1, E(F) has a proper edge coloring $\phi$ such that $\phi (uv)\in L(uv)$ for each $uv\in E(F)$. We use the coloring $\phi$ of F to color the edges of $H'$ and combine the coloring $\varphi$ of $G'$ to obtain an equitable k-edge-coloring of G, a contradiction. $\square$

By Lemma 7, the following corollary is immediate.

Corollary 2

Each i-vertex with $2\le i\le 5$ has one j-master with $i\le j\le 5$.

Since $G^{\times }$ is a plane graph, by Euler’s formula, we have

$$\begin{aligned} \sum _{v\in V(G)}(d_{G}(v)-4)+\sum _{f\in F(G^{\times })}(d_{G^{\times }}(f)-4)=-8. \end{aligned}$$

Now we use the method of redistribution of charge in order to obtain a contradiction. We assign an “ initial charge$''$ c(x) to each element $x\in V(G)\cup F(G^{\times })$, where

$$\begin{aligned} c(x)=d(x)-4, \quad \hbox { if }\;x\in V(G)\cup F(G^{\times }). \end{aligned}$$

We shall now redistribute the charge based on following discharging rules, without changing the total sum, in such a way that the sum is provably positive, and this contradiction will prove the theorem. Let $c'(x)$ be the resulting charge on $x\in V(G)\cup F(G^{\times })$. In what follows, we check that $c'(x)\ge 0$ for every $x\in V(G)\cup F(G^{\times })$.

R1. :

Each k-face f with $k\ge 5$ in $G^{\times }$ sends $\frac{k-4}{t(f)}$ to each 3-vertex incident with it, where t(f) is the number of 3-vertices incident with the face f;

R2. :

Each 2-vertex in G receives $\frac{2}{3}$ from its 2-master, $\frac{1}{3}$ from its 3-master, $\frac{2}{3}$ from its 4-master, and $\frac{1}{3}$ from its 5-master;

R3. :

Each 3-vertex in G receives $\frac{1}{3}$ from its 3-master, $\frac{2}{3}$ from its 4-master, $\frac{1}{3}$ from its 5-master and sends $\frac{1}{3}$ to each type one 3-face incident with it in $G^{\times }$;

R4. :

Each 4-vertex in G receives $\frac{2}{3}$ from its 4-master, $\frac{1}{3}$ from its 5-master and sends $\frac{1}{3}$ to each type one 3-face incident with it in $G^{\times }$;

R5. :

Each 5-vertex in G receives $\frac{1}{3}$ from its 5-master and sends $\frac{1}{3}$ to each type one 3-face incident with it in $G^{\times }$;

R6. :

Each 6-vertex in G sends $\frac{1}{3}$ to each type one 3-face incident with it in $G^{\times }$;

R7. :

Each 7-vertex in G sends $\frac{1}{2}$ to each type one 3-face incident with it in $G^{\times }$;

R8. :

Each d-vertex in G with $8\le d\le 16$ sends $\frac{1}{2}$ to each 3-face incident with it in $G^{\times }$;

R9. :

Each d-vertex in G with $d\ge 17$ sends $\frac{2}{3}$ to each type one 3-face, $\frac{1}{2}$ to each type two 3-face incident with it in $G^{\times }$;

Let v be a vertex in G with degree d. If $d=2$, then every 2-vertex has one j-master for each $2\le j\le 5$ by Corollary 2, and it follows that $c'(v)=2-4+\frac{2}{3}+\frac{1}{3}+\frac{2}{3}+\frac{1}{3}=0$ by R2. Suppose that v is 3-vertex. Then it has one 3-master, one 4-master and one 5-master by Corollary 2, so v receives totally $\frac{4}{3}$ from its masters by R3. If $n_c(v)=3$, then $f_3(v)=0$ by (a) of Lemma 2 and then v sends out none. So $c'(v)=-1+\frac{4}{3}>0$. If $n_c(v)=2$, then by (a) of Lemma 2, $f_3(v)\le 2$. If $f_3(v)\le 1$, then $c'(v)=-1+\frac{4}{3}-\frac{1}{3}=0$ by R3. If $f_3(v)=2$, then by (c) of Lemma 2, v must be incident with a $5^+$-face f. It follows that v receives at least $\frac{1}{2}$ from f by R1. So $c'(v)\ge -1+\frac{4}{3}-\frac{2}{3}+\frac{1}{2}>0$. If $n_c(v)\le 1$, then by (d) of Lemma 2, v is incident with at most one type one 3-face, which implies that $c'(v)\ge -1+\frac{4}{3}-\frac{1}{3}=0$ by R3. If $d=4$, then v is incident with at most three type one 3-faces by Lemma 3, and v has a 4-master and a 5-master by Corollary 2, so $c'(v)\ge 0-3\times \frac{1}{3}+\frac{2}{3}+\frac{1}{3}=0$ by R4. If $d=5$, then v is incident with at most four type one 3-faces by Lemma 3 and v has a 5-master by Corollary 2, so $c'(v)\ge 1-4\times \frac{1}{3}+\frac{1}{3}=0$ by R5. If $d=6$, then $c'(v)\ge 2-6\times \frac{1}{3}=0$ by R6. If $d=7$, then any 7-vertex v is incident with at most six type one 3-faces by Lemma 3, and it follows that $c'(v)\ge 3-6\times \frac{1}{2}=0$ by R7. If $8\le d\le 16$, then v cannot be a master of some other vertex in G by Lemmas 6 and 7, and it follows that $c'(v)\ge d-4-\frac{1}{2}d=\frac{d-8}{2}\ge 0$ by R8.

If $d=17$, then the neighbors of v are of degree at least 6 by Lemma 6. By R9, $c'(v)\ge 13-17\times \frac{2}{3}>0$.

If $d=18$, then the neighbors of v are of degree at least 5 by Lemma 6. By Lemma 7, v can be 5-master of at most four vertices and cannot be i-master with $2\le i\le 4$. By R2–R5 and R9, $c'(v)\ge 14-\frac{1}{3}\times 4-18\times \frac{2}{3}>0$.

If $d=19$, then the neighbors of v are of degree at least 4 by Lemma 6. By Lemma 7, v can be 5-master of at most four vertices, and 4-master of at most three vertices. By R2–R7, v sends out at most $4\times \frac{1}{3}+3\times \frac{2}{3}=\frac{10}{3}$ as masters. If $f_3(v)\le 17$, then $c'(v)\ge 15-\frac{10}{3}-\frac{2}{3}\times 17=\frac{1}{3}>0$ by R9. If $f_3(v)\ge 18$, then $c'(v)\ge 15-\frac{10}{3}-\frac{2}{3}\lceil \frac{f_3(v)}{2}\rceil -\frac{1}{2}(f_3(v)-\lceil \frac{f_3(v)}{2}\rceil )\ge \frac{1}{2}>0$ by Lemma 4 and R9.

If $d=20$, then the neighbors of v are of degree at least 3 by Lemma 6. By Lemma 7, v can be 5-master of at most four vertices, 4-master of at most three vertices, and 3-master of at most two vertices. By R2–R7, v sends out at most $4\times \frac{1}{3}+3\times \frac{2}{3}+2\times \frac{1}{3}=4$ as masters. If $f_3(v)\le 18$, then $c'(v)\ge 16-4-\frac{2}{3}\times 18=0$ by R9. If $f_3(v)\ge 19$, then $c'(v)\ge 16-4-\frac{2}{3}\lceil \frac{f_3(v)}{2}\rceil -\frac{1}{2}(f_3(v)-\lceil \frac{f_3(v)}{2}\rceil )\ge \frac{1}{3}$ by Lemma 4 and R9.

If $d\ge 21$, then the neighbors of v are of degree at least 2 by Lemma 6. By Lemma 7, v can be 5-master of at most four vertices, 4-master of at most three vertices, 3-master of at most two vertices, and 2-master of at most one vertex. By R2–R7, v sends out at most $4\times \frac{1}{3}+3\times \frac{2}{3}+2\times \frac{1}{3}+1\times \frac{2}{3}=\frac{14}{3}$ as masters. If $f_3(v)\le d-3$, then $c'(v)\ge d-4-\frac{14}{3}-\frac{2}{3}f_3(v)\ge \frac{1}{3}(d-20)>0$ by R9. If $d-2\le f_3(v)\le d-1$, then $c'(v)\ge d-4-\frac{14}{3}-\frac{2}{3}(\lceil \frac{f_3(v)}{2}\rceil +1)-\frac{1}{2}(f_3(v)-\lceil \frac{f_3(v)}{2}\rceil -1)\ge \frac{1}{12}(5d-99)>0$ by Lemma 4 and R9. If $f_3(v)=d$, then $c'(v)\ge d-4-\frac{14}{3}-\frac{2}{3}(\lfloor \frac{f_3(v)}{2}\rfloor )-\frac{1}{2}(f_3(v)-\lfloor \frac{f_3(v)}{2}\rfloor )\ge \frac{1}{12}(5d-104)>0$.

We now check that $c'(f)\ge 0$ if f is a 3-face or a 4-face. First of all, $c'(f)=c(f)=0$ for any 4-face f since f is not involved in above discharging rules. In what follows, we assume that f is a 3-face.

Checking 3-faces: Suppose that $f=uvw$ is of type one with crossing vertex u, $7^-$-vertex v and $8^+$-vertex w. If $d_{G^{\times }}(v)\le 6$, then $d_{G^{\times }}(w)\ge 17$ by Lemma 6. By R3–R6 and R9, v and w sends $\frac{1}{3}$ and $\frac{2}{3}$ to f, respectively, which implies that $c'(f)=-1+\frac{1}{3}+\frac{2}{3}=0$. If $d_{G^{\times }}(v)=7$, then $d_{G^{\times }}(w)\ge 16$ by Lemma 6. By R7, v sends $\frac{1}{2}$ to f, and by R8 and R9, w sends at least $\frac{1}{2}$ to f. This implies that $c'(f)\ge -1+\frac{1}{2}+\frac{1}{2}=0$. One the other hand, Suppose that $f=uvw$ is of type two. If u is a crossing vertex, then v and w are both big, so by R8 and R9, each of them sends $\frac{1}{2}$ to f. This implies that $c'(f)= -1+\frac{1}{2}+\frac{1}{2}=0$. Hence we assume that f is not incident with a crossing vertex. Under this condition, at least two vertices among u, v and w, say v and w, are big, since any two $7^-$-vertices are not adjacent in G by Lemma 6. By R8 and R9, each of v and w sends at least $\frac{1}{2}$ to f. This implies that $c'(f)\ge -1+\frac{1}{2}+\frac{1}{2}=0$.

Till now, we have checked that $c'(x)\ge 0$ for all $x\in V(G)\cup F(G^{\times })$. Hence, this completes the proof of Theorem 1. $\square$

3 Planar Graphs

A 2-alternating cycle in a graph G is a cycle of even length in which alternate vertices have degree 2 in G. A 3-alternator is a bipartite subgraph F of G with partite sets U, W such that, for each $u\in U$, $2\le d_F(u)= d_G(u)\le 3$, and for each $w\in W$, either $d_F (w)\ge 3$ or w has exactly two neighbours in U, both with degree exactly $14-d_G(w)$ (this last being possible only if $d_G(w)=11$ or 12).

Lemma 8

[1] Let H be a simple graph embedded in a surface of nonnegative characteristic and $\delta (H)\ge 2$. Then H contains a 2-alternating cycle, or a 3-alternator, or an edge $e=uw$ such that $d_H(u)+d_H(w)\le 13$.

Theorem 3

If G is a planar graph, then $\chi '_{\equiv }(G)\le 12$.

Proof

The proof is carried out by contradiction. Let G be a minimal counterexample to the theorem in terms of the number of vertices and edges. Let $C=\{1,2,\ldots , k\}$ be the color set with $k\ge 12$. It is obvious that G is connected. By Lemma 5, we have $\delta (G) \ge 2$. By Lemma 8, we consider the following three cases.

Case 1. G has an edge uv with $d_G(u)\le d_G(v)$ and $d_G(u)+ d_G(v) \le 13$.

The case can be settled similar to Lemma 6.

Case 2. G contains an even cycle $C= v_{1} v_{2} \cdots v_{2n}v_{1}$ with $d(v_{1})= d(v_{3})= \cdots = d(v_{2n-1})= 2$.

Then $G'=G-E(C)$ has an equitable edge-coloring $\varphi$ with k colors by the minimality of G. For every $i(1\le i\le n)$, let $L(v_{2i}v_{2i-1})=L(v_{2i}v_{2i+1})=\{\alpha , \beta \}$, where $\alpha \in C_\varphi (v_{2i})$ and

$$\begin{aligned} \beta \in \left\{ \begin{array}{ll} C_\varphi (v_{2i})\backslash \alpha , &{} \quad \hbox {if } \; |C_\varphi (v_{2i})|\ge 2; \\ C\backslash C_\varphi (v_{2i}), &{} \quad \hbox {otherwise.} \end{array} \right. \end{aligned}$$

So $f(v_iv_{i+1})=|L(v_iv_{i+1})|=2$. By Lemma 1, E(C) has a proper edge coloring $\phi$ such that $\phi (e)\in L(e)$ for each edge e of C. By combining $\phi$ and $\varphi$, we obtain an equitable k-edge-coloring of G, a contradiction.

Case 3. G contains a 3-alternator F with partite sets X, Y such that for each $u\in X$, $2\le d_F(u)= d_G(u)\le 3$, and for each $w\in Y$, either $d_F (w)\ge 3$ or w has exactly two neighbours in X, both with degree exactly $14-d_G(w)$ (this last being possible only if $d_G(w)=11$ or 12).

By the minimality of G, $G'=G-X$ has an equitable k-edge-coloring $\varphi$. In the following, we will color E(F) equitably. For every $y \in Y$ satisfying $d_{F}(y) =d>k$, let $d=ak+b(a\ge 1, b\ge 0, a+b\ge 2)$, we split y into $a+1$ vertices $y_1, y_2,\ldots , y_{a+1}$ of degree $s, t, k, k, \ldots , k$, respectively, such that $s\ge 3, t\ge 3$ and $s+t=k+b$. We call $y_i$ the ith splitting vertices of $y(1\le i\le a+1)$ and the new bipartite graph obtained by the splitting operation is denoted by $F'=(X, Y')$. Then $d_{F'}(x)=d_G(x) \le 3$ for each $x \in X$ and $3\le d_{F'}(y) \le k$ for each $y \in F'$. We define the list L(uv) of the edge uv of $F'$, $u\in X, y\in Y'$ as follows.

• Suppose that $d_{F'}(v)=d_{F}(v)$. Then $d_{F'}(v)\le k$. First, we put all colors of $C_{\varphi }(v)$ into L(uv). If $\max \{d_{F'}(v), d_{F'}(u)\}=t>|C_{\varphi }(v)|$, then we choose $t-|C_{\varphi }(v)|$ colors from $C\backslash C_{\varphi }(v)$ to put into L(uv);

• Suppose that v is the first splitting vertex of some vertex y of Y. If $d_{F'}(v)\le |C_{\varphi }(y)|$, then we choose $d_{F'}(v)$ colors from $C_{\varphi }(y)$ to put into L(uv). Otherwise, we put all colors of $C_{\varphi }(y)$ into L(uv) and then we choose $d_{F'}(v)-|C_{\varphi }(v)|$ colors from $C\backslash C_{\varphi }(y)$ to put into L(uv);

• Suppose that v is the second splitting vertex of some vertex y of Y. Let $v'$ be the first splitting vertex of y and $u'\in N_{F'}(v')$. First, we put all colors of $C\backslash L(u'v')$ into L(uv). If $d_{F'}(v)+d_{F'}(v')\le k+|C_{\varphi }(y)|$, then we choose $d_{F'}(v)+d_{F'}(v')- k$ colors from $C_{\varphi }(y)\cap L(u'v')$ to put into L(uv). Otherwise, we put first all colors of $C_{\varphi }(y)$ into L(uv) and then we choose $d_{F'}(v)+d_{F'}(v')-k-|C_{\varphi }(y)|$ colors from $L(u'v')\backslash C_{\varphi }(y)$ to put into L(uv);

• For some other splitting vertex v, we define $L(uv)= C$;

It is obvious that $|L(uv)|\ge \max \{d_{F'}(v), d_{F'}(u)\}$ for any uv of $F'$ where $u\in X, y\in Y'$. By Lemma 1, $E(F')$ has a proper edge coloring $\phi$ such that $\phi (uv)\in L(uv)$ for each $uv\in E(F')$. We use the coloring $\phi$ of $F'$ to color F and combine the coloring $\varphi$ of $G'$ to obtain an equitable k-edge-coloring of G, a contradiction.

Hence, this completes the proof of the Theorem 3. $\square$

4 Conclusions

For planar graphs, Vizing [2] conjectured that every planar graph with maximum degree 6 or 7 is of class 1. The case $\Delta =7$ for the conjecture has been verified by Zhang [10] and, independently, by Sanders and Zhao [6]. In the paper, we prove that every planar graph has an equitable edge-coloring with k colors for any integer $k\ge 12$. We pose the following conjecture.

Conjecture 4

If G is a planar graph, then $\chi '_{\equiv }(G)\le 6$.