ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 279-286
Edge looseness of plane graphs
Julius Czap
Department of Applied Mathematics and Business Informatics, Faculty of Economics Technical University ofKosice, Nemcovej 32, 040 01 Kosice, Slovakia
Received 7 February 2014, accepted 15 April 2015, published online 8 July 2015
A face of an edge colored plane graph is called e-loose if the number of colors used on its edges is at least three. The e-looseness of a plane graph G is the minimum positive integer k such that any edge coloring of G with k colors involves an e-loose face. In this paper we determine tight lower and upper bounds for the e-looseness of connected plane graphs. These bounds are expressed by linear polynomials of the number of faces.
Keywords: Plane graph, edge coloring. Math. Subj. Class.: 05C10, 05C15
1 Introduction
We use the standard terminology according to Bondy and Murty [1]. All considered graphs are undirected, finite, loopless, multiple edges are allowed.
Let G = (V, E, F ) denote a connected plane graph with the vertex set V, the edge set E and the face set F. We say that two edges of G are face-independent if they are not incident with the same face. Two edges of G are face-adjacent if they are consecutive edges of a facial trail of some face. The medial graph M ( G) of G is the simple graph obtained as follows. For each edge e of G insert a vertex m(e) in M (G). Join two vertices of M (G) if the corresponding edges are face-adjacent in G. The embedding of G induces the embedding of M (G).
Edge colorings of graphs embedded on surfaces with face-constrains have recently drawn a substantial amount of attention, see [5, 6, 7, 12] and references therein. There are two questions derived from hypergraph colorings that one may ask in this setting:
Question 1.1. What is the minimum number of colors needed to color the edges of a connected plane graph in such a way that each of its faces is incident with edges of at least two different colors?
E-mail address: julius.czap@tuke.sk (Julius Czap)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
280
Ars Math. Contemp. 9 (2015) 165-186
Question 1.2. What is the maximum number of colors that can be used in an edge coloring of a connected plane graph in such a way that each of its faces is incident with edges of at most two different colors?
The following result gives the answer to Question 1.1.
Theorem 1.3. Every connected plane graph (on at least two edges) has an edge coloring with at most 3 colors such that each of its faces is incident with edges of at least two different colors. Moreover, if G is simple, then 2 colors are sufficient.
Proof. First we show that every connected plane graph without faces of size two has an edge coloring with 2 colors such that these two colors appear on every face. Let G be such a plane graph and let M(G) be its medial graph. Add edges to M(G) to obtain a plane triangulation T. By the Four Color Theorem, T has a proper vertex coloring which uses 3 or 4 colors. Combine the first color class with the second, and combine the third with the fourth. This yields a 2-coloring of the graph T. It is easy to check that each face of T is incident with vertices of two different colors. This vertex coloring induces a required edge coloring of G.
Now assume that the claim does not hold for a connected plane graph with faces of size two. Let G be a counterexample on minimum number of edges. Let e be an edge which is incident with faces f and g, where f has size two. Let G - e be the graph obtained from G by removing the edge e. The graph G - e is not a counterexample because it has fewer edges than G. Consequently, it has a required coloring. Let h be the face in G - e corresponding to the faces f and g in G. Extend the coloring of G - e to a coloring of G in the following way. If two colors appear on h, then color e with the third color. Otherwise (three colors appear on h) we color e with a color which does not appear on the second edge of f. This means that the minimum counterexample does not exist.
There are graphs which require three colors for such a coloring, for example the connected graph on two vertices and three edges.	□
In this paper, we focus on Question 1.2. A face of an edge colored plane graph is called monochromatic or bichromatic if the number of colors used on its edges is one or two, respectively. A face which is neither monochromatic nor bichromatic is called edge loose (or shortly e-loose). The edge looseness (or shortly e-looseness) of a plane graph G is the minimum positive integer k such that any surjective k-edge-coloring involves an e-loose face. This parameter of G will be denoted by els(G). The e-looseness is well defined for all plane graphs having at least one face incident with at least three different edges. (Note that every connected plane graph on at least four vertices has such a face.) Throughout the paper, we will consider only such graphs.
2 Upper bounds
2.1 1-connected plane graphs
Theorem 2.1. Let G = (V, E, F) be a connected plane graph. Then els(G) < |F| + 2. Moreover, this bound is sharp.
Proof. Let ^ be an edge coloring of G such that each of its faces is either monochromatic or bichromatic. First we show that ^ uses at most |F| + 1 colors. Clearly, we can assume that ^ uses at least two colors. This means that at least one face is bichromatic, say fi. Let
J. Czap: Edge looseness of plane graphs
281
/2 be a face of G adjacent to /1. There is at most one color which appears on /2 and does not appear on /1, since the faces /1 and /2 share an edge and at most two colors occur on /2. The graph G is connected, therefore we can number the faces /1, /2,..., /|F | of G such that for every i > 2 the face / is adjacent to a face / for some j < i. Using the argument described above, there is at most one color which appears on / and does not appear on /1;..., /j-1. Consequently, ^ uses at most 2 + (|F| — 1) colors. This means that every edge coloring with at least |F | + 2 colors involves an e-loose face.
Now we prove that this upper bound is tight. Let H be a connected plane graph on at least three vertices. We insert a new vertex into each face of H and join each new vertex by an edge inside the corresponding face to exactly one of its vertices. In this way we obtain a 1-connected plane graph H. Clearly, we added |F(H)| edges to H and these new edges are face-independent in H. If we color these face-independent edges with distinct colors and all other edges with the same color, then we obtain an edge coloring of H such that every face is bichromatic. Hence, els(H) > |F(H)| + 2 = |F(H)| +2.	□
2.2 2-connected plane graphs
When G is 2-connected, the bound from Theorem 2.1 can be improved by one.
Let us recall that the (geometric) dual G* = (V*,E*,F*) of a plane graph G = (V, E, F) can be defined as follows: Corresponding to each face / of G there is a vertex /* of G*, and corresponding to each edge e of G there is an edge e* of G*; two vertices /* and g* are joined by the edge e* in G* if and only if their corresponding faces / and g are separated by the edge e in G (an edge separates the faces incident with it).
Theorem 2.2. Let G = (V, E, F) be a 2-connected plane graph. Then els(G) < |F | + 1. Moreover, this bound is sharp.
Proof. Let ^ be an edge coloring of G such that every face is either monochromatic or bichromatic. This coloring induces a coloring of the dual G* in a natural way. Observe that at most 2 colors appear at any vertex of G*. Let us choose one edge from each color class, and let the chosen edges induce the subgraph H of G*. Each component of H is either a path or a cycle, since the graph G* does not contain any loop. Therefore, 2|E(H )| = (H) degH (v) < 2|V (H)| < 2|V (G*)| = 2|F (G)|. Since the number of colors used by ^ equals |E(H) |, we deduce that ^ uses at most |F(G) | colors.
To see that the bound is tight consider the plane embedding of the complete bipartite graph K2 n, see Figure 1. This plane graph has n faces and an n-edge-coloring such that every face is bichromatic.	□
Figure 1: A plane drawing of K2,
282
Ars Math. Contemp. 9 (2015) 165-186
2.3 3-connected plane graphs
Lemma 2.3. Let G = (V, E, F) be a 3-connected plane triangulation. Let t denote the maximum number of disjoint cycles in its dual. Then els(G) = 1 |F | + 1 +1.
Proof. Any M2-edge coloring (being an edge coloring of a graph such that at most 2 colors appear at any vertex, see [2, 3]) of the dual graph G* corresponds to an edge coloring of G with property that every face of G is incident with edges of at most two different colors and vice versa. The graph G* is cubic, since G is a plane triangulation. In [3], it was proved that the maximum number of colors that can be used in an M2-edge coloring of a cubic plane graph H is equal to J-^^ +1, where t is the maximum number of disjoint cycles in H. Consequently, els(G) =	+1 + 1 = ^^ +1 + 1.	□
Theorem 2.4. Let G = (V, E, F) be a 3-connected plane triangulation. Let g denote the girth of its dual. Then
•	els(G) < | |F| + 1 if g > 3,
•	els(G) < 4 |F| + 1 if g > 4,
•	els(G) < 10|F| + 1 if g > 5.
Moreover, these bounds are sharp.
Proof. It follows from Lemma 2.3, since the number of disjoint cycles in the dual G* is not greater than |V {f]l = JFp.
By Lemma 2.3 we can easily prove that the bounds are attained on the duals of graphs shown in Figure 2.	□
Figure 2: The duals of these graphs show that the bounds are tight.
Conjecture 2.5. Let G = (V, E, F) be a 3-connected plane graph. Then els(G) < 6 |F | + 1.
3 Lower bounds
A matching of G is a set of pairwise disjoint edges, and a maximum matching is one of maximum cardinality.
Let c(H) denote the number of components of a graph H.
Lemma 3.1. Let G be a connected plane graph and let G* be its dual. Let M* be a matching in G*. Then els(G) > |M* | + c(G* - M*) + 1. Moreover, this bound is sharp.
J. Czap: Edge looseness of plane graphs
283
Proof. We color the edges of the matching M* with distinct colors and use an additional new color for the edges of each component of G* — M*. Thus, we obtain an edge coloring of the dual graph G* such that at most 2 colors appear at any vertex of G*. This coloring induces a coloring of G in which every face is either monochromatic or bichromatic.
To see that the bound is sharp, let G be a plane graph whose dual is a 2r-sided prism. The 2r-sided prism H2r, r > 2, consists of the vertex set V = jwi, u2,..., u2r, vi, v2,..., v2r } and the edge set E = {uiui+1,vivi+1, uiv^i = 1,..., 2r}, where 2r + 1 := 1. The set of faces consists of two 2r-gonal faces f1 = [u1,..., u2r] and f2 = [v1,..., v2r] and 2r quadrangles [uiui+1 vi+1vi] for i = 1,2,..., 2r, see Figure 3 for illustration.
Figure 3: A 2r-sided prism.
Let M = {uiui+1, vivi+1|i = 1,3, 5,..., 2r - 1} be a matching of H2r. Observe that |M| = 2r and c(H2r — M) = r. Therefore els(G) > 3r +1. On the other hand, the graph H2r is a simple 3-connected cubic plane graph, hence its dual (the graph G) is a simple triangulation. By Theorem 2.4 we have els(G) < | • 4r +1.	□
Corollary 3.2. Let G be a connected plane graph and let G* be its dual. Let M* be a maximum matching in G*. Then els(G) > |M*| + 2.
Proof. It immediately follows from Lemma 3.1, since c(G* — M*) > 1.	□
Since there are 2-connected (and 1-connected) graphs G with arbitrarily many faces which have els(G) < 4 (Take a plane drawing of the cycle C = v1v2... v3n. Add n vertices u1, u2,..., un to the inner part of C and join ui with v3i-2 and v3i as it is depicted in Figure 4. It is easy to see that the e-looseness of the obtained graph is four.), there is no nontrivial lower bound on els(G) expressed by a linear polynomial of |F| if G is not 3-connected. Hence, in the remaining part of the paper we will investigate e-looseness of 3-connected plane graphs G. Since the dual of G is a simple plane graph, we may apply structural properties of planar graphs on the dual graph; in particular, we will use the following one.
V5
Figure 4: A graph G with "many" faces and els(G) = 4.
284
Ars Math. Contemp. 9 (2015) 165-186
Theorem 3.3. [11] Let G be an n-vertex 3-connected planar graph with n > 78. Let S denote the minimum degree of G and let M be a maximum matching in G. Then,
•	|M | > n+4 if S > 3,
•	|M | > 3n+8 if S > 4,
•	|M | > ^n+o if s > 5.
|V (G)l 2
Note that, if a planar graph G is 4-connected, then it has a matching of size This immediately follows from Tutte's result [14]: every 4-connected planar graph contains a Hamiltonian cycle.
Lemma 3.4. Let G = (V, E, F) be a 3-connected plane graph. Then it has at least lV§1 + 2 faces. Moreover, this bound is tight.
Proof. The minimum degree of G is at least 3, since it is 3-connected. Using the hand
deg(v) > 3|V|. Consequently, |E| > §
shaking lemma we have 2|E| = ^2v9V deg(v) > 3|V |. Consequently, |E | > | |V |. Using
this fact and the Euler's polyhedral formula | V| - |E| + |F| = 2 we obtain |F| > 2 + ^. This bound is attained for every 3-connected cubic plane graph.	□
Using Corollary 3.2, Theorem 3.3 and Lemma 3.4 we can prove the following.
Theorem 3.5. Let G = (V, E, F) be a 3-connected plane graph on at least 152 vertices. Let g be the girth of G. Then,
•	els(G) > ^f4 +2 if g > 3,
•	els(G) >	+ 2 if g > 4,
•	els(G) > ^Ff20 +2 if g > 5. Moreover, these bounds are sharp.
Proof. The 3-connectedness of G implies that its dual G* is also 3-connected, hence we can use Theorem 3.3 for G*. By Lemma 3.4, |V(G* )| = |F(G)| > + 2 > 78. It is easy to check that ^f4 < < 9n+§0 for n > 2. As g(G) < J(G*), the result follows from Corollary 3.2 and Theorem 3.3. The sharpness of these bounds follows from Theorem 3.6.	□
Theorem 3.6. For any integer n > 4 there exists a 3-connected cubic plane graph G = (V, E, F) with girth g such that
•	g = 3, |F| = 3n - 4 and els(G) = n + 2,
•	g = 4, |F| = 7n - 12 and els(G) = 3n - 2,
•	g = 5, |F| = 19n - 36 and els(G) = 9n - 14.
Proof. Let T be a simple plane triangulation on n > 4 vertices. Let Gj be the graph obtained from T by inserting the configuration Hi, shown in Figure 5, into each of its faces,
for i = 3,4, 5.
Any plane triangulation on n vertices has 2n - 4 faces, therefore |F(G£)| = |V(G3)| = n + 2n - 4 = 3n - 4,
J. Czap: Edge looseness of plane graphs
285
|F(GDI = |V(G4)| = n + 3(2n - 4) = 7n - 12 and |F(G;t)| = |V(g5)| = n + 9(2n - 4) = 19n - 36.
In [2] it was proved that K2(G3) = n + 1, K2(G4) = 3n - 3 and K2(G5) = 9n - 15, where K2(Gj) denotes the maximum number of colors used in an M2-edge coloring of Gj, i = 3,4,5. Consequently, for the duals of these graphs it holds els(G*) = n + 2, els(G4) = 3n - 2 and els(G*) = 9n - 14.
Observe, that each minimum edge-cut of size g in Gj corresponds to a cycle in G* and vice versa, therefore, the edge connectivity of the graph Gj is equal to the girth of the dual graph G*. The edge connectivity of Gj is equal to i, for i = 3,4, 5, since the tetrahedron, octahedron and icosahedron have edge connectivities 3,4 and 5, respectively.	□
Finally, note that the vertex version of Question 1.2 was investigated in [4], where it was proved that the vertex looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. Vertex looseness of triangulations on closed surfaces was studied in [8, 9, 10, 13].
References
[1]	J.A. Bondy and U.S.R. Murty, Graph theory, Springer, New York, 2008.
[2]	K. Budajova and J. Czap, M2-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math 88 (2013), 161-167.
[3]	J. Czap, Mi-edge colorings of graphs, Appl. Math. Sciences 5 (2011), 2437-2442.
[4]	J. Czap, S. Jendrol', F. Kardos and J. Miskuf, Looseness of plane graphs, Graphs Combin. 27 (2011), 73-85.
[5]	S. Jendrol', J. Miskuf, R. Sotak and E. Skrabul'akova, Rainbow faces in edge-colored plane graphs, J. Graph Theory 62 (2009), 84-99.
[6]	B. Luzar, M. Mockovciakova, R. Sotak, R. Skrekovski and P. Sugerek, ¿-facial edge colorings of graphs, Discrete Appl. Math. 181 (2015), 193-200.
[7]	B. Luzar and R. Skrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013), 2218-2222.
[8]	K. Matsuoka, Looseness width of 5-connected triangulations on the torus, Electron. Notes Discrete Math. 31 (2008), 105-108.
[9]	S. Negami, Looseness ranges of triangulations on closed surfaces, Discrete Math. 303 (2005), 167-174.
[10] S. Negami and T. Midorikawa Loosely-tightness of triangulations of closed surfaces, Sci. Rep. Yokohama Nat. Univ., Sect. I, Math. Phys. Chem. 43 (1996), 25-41.
286
Ars Math. Contemp. 9 (2015) 165-186
[11]	T. Nishizeki and I. Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Math. 28 (1979), 255-267.
[12]	J. Przybylo, On the facial Thue choice index via entropy compression, J. Graph Theory 77 (2014), 180-189.
[13]	T. Tanuma, One-loosely tight triangulations of closed surfaces, Yokohama Math. J. 47 (1999), 203-211.
[14]	W.T. Tutte, A theorem on planar graphs, Trans. Am. Math. Soc. 82 (1956), 99-116.