- Email: [email protected]

Contents lists available at ScienceDirect

Information Processing Letters www.elsevier.com/locate/ipl

On purely tree-colorable planar graphs Jin Xu a,b,∗ , Zepeng Li a,b , Enqiang Zhu a,b a b

School of electronics and computer science, Peking University, Beijing 100871, China Key Laboratory of High Conﬁdence Software Technologies (Peking University), Beijing 100871, China

a r t i c l e

i n f o

Article history: Received 14 November 2014 Received in revised form 13 March 2016 Accepted 24 March 2016 Available online 29 March 2016 Communicated by X. Wu Keywords: Combinatorial problems Maximal planar graph (MPG) Tree-k-coloring Purely tree-k-colorable Dumbbell-maximal planar graph (dumbbell-MPG)

a b s t r a c t A tree-k-coloring of a graph G is a k-coloring of G such that the subgraph induced by the union of any two color classes is a tree. G is purely tree-k-colorable if the chromatic number of G is k and any k-coloring of G is a tree-k-coloring. Xu [16] conjectured that there exist only two purely tree-4-colorable 4-connected maximal planar graphs. In this paper, we construct an inﬁnite family of purely tree-colorable 4-connected maximal planar graphs, called dumbbell-maximal planar graphs, which disprove Xu’s conjecture. Moreover, we give the enumeration of dumbbell-maximal planar graphs and propose a conjecture on such graphs. It turns out that the conjecture implies naturally the uniquely 4-colorable planar graph conjecture. © 2016 Elsevier B.V. All rights reserved.

1. Introduction All graphs considered in this paper are ﬁnite, simple and undirected, and we follow [1] for the terminologies and notations not deﬁned here. Given a graph G, we use V (G ), E (G ) and δ(G ) (or simply V , E and δ if the graph is clear from the context) to denote the vertex set, the edge set and the minimum degree of G, respectively. A subgraph H of G is called an induced subgraph if for any u , v ∈ V ( H ), u , v are adjacent in G if and only if they are adjacent in H ; we also say H is a subgraph induced by V ( H ) in the traditional sense, written as H = G [ V ( H )]. A k-path (or k-cycle) is a path (or cycle) of length k. An n-wheel is a graph on n + 1 vertices, which is constructed by an n-cycle and a more vertex adjacent to each vertex of the cycle. A planar graph is a graph that can be drawn in the plane so that its edges intersect only at their ends. A graph is called a maximal planar graph (MPG) or a triangulation if

*

Corresponding author. E-mail addresses: [email protected] (J. Xu), [email protected] (Z. Li), [email protected] (E. Zhu). http://dx.doi.org/10.1016/j.ipl.2016.03.011 0020-0190/© 2016 Elsevier B.V. All rights reserved.

it is planar but adding any edge (on the given vertex set) would destroy that property. If an MPG can be reduced into the tetrahedral graph by deleting a 3-vertex and its incident edges, repeatedly, then we call this graph a recursive MPG, where a k-vertex of a graph G is a vertex with degree k. A cycle C of a planar graph is separating if there exist vertices in the interior and the exterior of C . A k-coloring of G is an assignment of k colors to V (G ) such that no two adjacent vertices are assigned the same color. Naturally, a k-coloring can be viewed as a partition { V 1 , V 2 , · · · , V k } of V , where V i denotes the set of vertices assigned color i, and is called a color class of the coloring for any i = 1, 2, · · · , k. A graph G is k-colorable if it admits a k-coloring. The chromatic number of G, denoted by χ (G ), is the minimum number k such that G is k-colorable. A graph G is uniquely k-colorable if χ (G ) = k and G has only one k-coloring up to permutation of the colors. The uniquely coloring problem of graphs was ﬁrst proposed by Cartwright and Harary [2] and Gleason and Cartwright [8]. In 1973, Greenwell and Kronk [11] studied the uniquely colorable graphs in terms of the edge coloring, and proposed a conjecture as follows.

J. Xu et al. / Information Processing Letters 116 (2016) 532–536

533

Conjecture 1.1. If G is a uniquely 3-edge-colorable cubic graph, then G is a planar graph that contains a triangle. In 1975, Fiorini [3] independently studied uniquely edge colorable graphs, and obtained some similar results to the ones of Greenwell and Kronk. After that, many scholars discussed this class of graphs, such as Thomason [14,15], Fiorini and Wilson [4,5], Zhang [18], and Goldwasser and Zhang [9,10]. In 1977, Fiorini and Wilson [4] put forward the following conjecture on the basis of Conjecture 1.1. Conjecture 1.2 (Uniquely 4-colorable planar graph conjecture: edge version). Every uniquely 3-edge-colorable cubic planar graph contains a triangle. Fisk [6] independently proposed a dual version of Conjecture 1.2, which characterizes the structure of uniquely 4-colorable planar graphs. Conjecture 1.3 (Uniquely 4-colorable planar graph conjecture: vertex version). A planar graph G is uniquely 4-colorable if and only if G can be obtained from K 4 by embedding a vertex of degree 3 in some triangular face continuously, that is, G is a recursive MPG. Goldwasser and Zhang [10] proved that every counterexample to Conjecture 1.3 is 5-connected. Fowler [7] investigated in detail the uniquely 4-colorable planar graphs by using a method similar to the proof of the 4-Color Theorem [13]. For a k-coloring f of a graph G, if the subgraph induced by the union of any two color classes under f is a tree, then we call f a tree-k-coloring of G. If the chromatic number of G is k and any k-coloring of G is a tree-k-coloring, then G is called purely tree-k-colorable. Note that a tree-k-coloring is also an acyclic k-coloring, which was introduced by Grunbaum [17]. By deﬁnition, it can be seen that each purely tree-k-colorable graph is connected. Moreover, we have the following Lemma 1.4, which is straightforward to prove. Lemma 1.4. If G is a purely tree-k-colorable graph on n vertices, then

1

| E (G )| = (k − 1)(2n − k). 2

Conversely, if G is uniquely k-colorable and | E (G )| = then for any k-coloring of G, the subgraph induced by the union of any two color classes is a tree. So we can obtain the following theorem. 1 (k − 1)(2n − k), 2

Theorem 1.5. If G is uniquely k-colorable and | E (G )| = 12 (k − 1)(2n − k), then G is purely tree-k-colorable. In this paper, we mainly consider the purely tree-4-colorable planar graphs. It is well known that the maximum number of edges in a planar graph with n ≥ 3 is 3n − 6, in which case the planar graph is maximal. Using this fact,

Fig. 1. Two purely tree-4-colorable MPGs J 9 and I 12 .

together with Lemma 1.4, we can conclude the following result. Corollary 1.6. Every purely tree-4-colorable planar graph is a maximal planar graph. In 2005, Xu [16] found two purely tree-4-colorable 4-connected maximal planar graphs (MPGs) J 9 and I 12 (icosahedron) shown in Figs. 1(a) and (b), and conjectured that there does not exist any purely tree-4-colorable MPG except for J 9 and I 12 . In this paper, we construct an inﬁnite family of purely tree-4-colorable 4-connected MPGs, called dumbbell-maximal planar graphs (dumbbell-MPGs), which disprove Xu’s conjecture. Moreover, we conjecture that a 4-connected MPG G is purely tree-4-colorable if and only if G is either the icosahedron or a dumbbell-MPG, which implies naturally the uniquely 4-colorable planar graph conjecture. 2. Purely tree-4-colorable planar graphs 2.1. Construction A dumbbell is a graph consisting of two triangles

v 1 v 2 u and uv 3 v 4 with exactly one common vertex u (see Fig. 2(a)). Obviously, a 4-wheel contains exactly two dumbbells. Without special assertion, dumbbells considered in this paper are ones contained in a 4-wheel. is deﬁned as follows. For The dumbbell transformation a given dumbbell X = v 1 v 2 u uv 3 v 4 , ﬁrst, add two 3-vertices x1 and x2 on the two triangular faces of X , respectively. Then split the vertex u into two vertices u and u , and split the edges xu and u y into two edges xu , xu and u y , u y respectively. Hence, the vertices x, u , y , u form a 4-cycle. Then add a new vertex v in this cycle adjacent to every vertex of the cycle. The process is shown in Figs. 2(a)–(c). It is easy to prove the following theorem. Theorem 2.1. Let G be an MPG with a 4-wheel W 4 . Then the graphs obtained from G by implementing the dumbbell transformations on two dumbbells of W 4 are isomorphic. A graph G is a dumbbell-MPG if either G is isomorphic to J 9 , or G can be obtained from a dumbbell-MPG by implementing a dumbbell transformation. We denote by J n a dumbbell-MPG on n vertices. For instance, Fig. 3(c) is a dumbbell-MPG on 13 vertices, which can be obtained

534

J. Xu et al. / Information Processing Letters 116 (2016) 532–536

Fig. 2. The dumbbell transformation.

Fig. 3. The process of generating J 13 from J 9 .

Fig. 4. The local structures of J 4k−3 and J 4k+1 .

from J 9 by implementing a dumbbell transformation (see Figs. 3(a)–(c)). Since J 9 has exactly 3 vertices of degree 4, by the deﬁnition of dumbbell-MPGs, we can obtain the following observations. Observation 1. Any dumbbell-MPG has order 4k + 1, where k ≥ 2. Observation 2. Any dumbbell-MPG has exactly 3 vertices of degree 4. Furthermore, we can obtain the following theorem. Theorem 2.2. For any integer number k with k ≥ 2, J 4k+1 is purely tree-4-colorable and has exactly 2k−1 tree-4-colorings. Proof. By induction on the number k. It can been checked that J 9 has only two 4-colorings and both of them are tree-4-colorings. So the result is true when k = 2. Now we assume that k ≥ 3. Let J 4k+1 be a dumbbell-MPG on 4k + 1 vertices and {1, 2, 3, 4} be a set of colors. By deﬁnition, J 4k+1 can be obtained from a dumbbell-MPG J 4k−3 by implementing a dumbbell transformation. Figs. 4(a) and (b) show the local structures of J 4k−3 and J 4k+1 , respectively. By the induction hypothesis, J 4k−3 is purely

tree-4-colorable and has exactly 2k−2 tree-4-colorings. We ﬁrst prove that J 4k+1 is purely tree-4-colorable. Suppose that J 4k+1 has a 4-coloring f which is not a tree-4-coloring. Using the fact that an MPG has a disconnected bichromatic subgraph colored 1 and 2 if and only if it has a bichromatic cycle colored 3 and 4, we can obtain that their exists a bichromatic cycle C in J 4k+1 under f . Deﬁne a coloring f of J 4k−3 as follows. Let f (x) = f (x) if x ∈ V ( J 4k−3 ) ∩ V ( J 4k+1 ) and f (u ) = a, where a ∈ {1, 2, 3, 4} \ { f ( v i ) : i = 1, 2, 3, 4}. Since f is a 4-coloring of J 4k+1 , we have 2 ≤ |{ f (x1 ), f (u ), f (x2 ), f (u )}| ≤ 3. If |{ f (x1 ), f (u ), f (x2 ), f (u )}| = 2, that is, the 4-cycle x1 ux2 u x1 is a bichromatic cycle under f , then the 4-cycle v 1 v 2 v 3 v 4 v 1 is also a bichromatic cycle under f . By the deﬁnition of f , we can obtain that f is a 4-coloring of J 4k−3 which contains a bichromatic cycle v 1 v 2 v 3 v 4 v 1 . This is a contradiction. Now consider the case of |{ f (x1 ), f (u ), f (x2 ), f (u )}| = 3. Without loss of generality, let f (x1 ) = f (x3 ) = 1, f (u ) = 2 and f (u ) = 3. Then f ( v ) = 4; f ( v 1 ) = f ( v 3 ) = 4, f ( v 2 ) = 3, f ( v 4 ) = 2 or f ( v 2 ) = f ( v 4 ) = 4, f ( v 1 ) = 2, f ( v 3 ) = 3. If C has no vertex in { v , x1 , u , x2 , u }, then C is also a bichromatic cycle of f , a contradiction. If C has some vertices in { v , x1 , u , x2 , u }, then C passes through the path v 1 x1 vx2 v 3

J. Xu et al. / Information Processing Letters 116 (2016) 532–536

535

Fig. 5. Two tree-4-colorings of J 4k+1 extended from the restriction of g to J 4k−3 − u.

or v 2 x1 vx2 v 4 in J 4k+1 (see Figs. 4(b) and (c)). So C is colored by the colors 1 and 4 alternatively. By the deﬁnition of f , we have f (u ) = 1. So f is a 4-coloring of J 4k−3 which contains a bichromatic cycle passing through the path v 1 uv 3 or v 2 uv 4 . This is a contradiction. Therefore, J 4k+1 is purely tree-4-colorable. Now we prove that J 4k+1 has exactly 2k−1 tree-4-colorings. Let g be a tree-4-coloring of J 4k−3 with g ( v 1 ) = g ( v 3 ) = 4, g ( v 2 ) = 3 and g ( v 4 ) = 2 (see Fig. 5(a)). Then the restriction of g to J 4k−3 − u can be extended to two 4-colorings f 1 , f 2 of J 4k+1 (see Figs. 5(b) and (c)). Since g is a tree-4-coloring of J 4k−3 , g contains no bichromatic cycle. From Figs. 5(b) and (c) we can see that f i also contains no bichromatic cycle, where i = 1, 2. So both of f 1 and f 2 are tree-4-colorings of J 4k+1 . On the other hand, for two distinct tree-4-colorings g 1 , g 2 of J 4k−3 , the tree-4-colorings of J 4k+1 extended from the restrictions of g 1 , g 2 to J 4k−3 − u are distinct. So J 4k+1 has at least 2k−1 tree-4-colorings. Furthermore, there are exactly 2 tree-4-colorings of J 4k+1 corresponding to a tree-4-coloring of J 4k−3 . Therefore, J 4k+1 has exactly 2k−1 tree-4-colorings. 2 2.2. Enumeration Now we give a counting formula of the dumbbell-MPGs on 4k + 9 vertices, where k ≥ 0. Lemma 2.3. (See [12].) Let A (n, k) denote the number of nonnegative integer solutions of Diophantine equation k i =1 ixi = n. Then

A (n, 3) =

(n + 3)2 12

−

7 72

+

(−1)n 8

+

2 9

cos

2nπ 3

.

Lemma 2.4. (See [12].) The number of unordered partitions of an integer n such that each part is at most k is equal to the number of unordered partitions of n into k parts. Theorem 2.5. Let tk denote the number of dumbbell-MPGs on 4k + 9 vertices, where k ≥ 0. Then

tk =

(k + 3)2 12

−

7 72

+

(−1)k 8

+

2 9

cos

2kπ 3

.

Proof. Denote by C 1 , C 2 and C 3 the three 4-cycles of J 9 induced by the neighbors of the three vertices of degree 4, respectively. Then every dumbbell-MPG on 4k + 9 vertices

can be obtained from J 9 by implementing ki dumbbell transformations in C i , where 3

ki = k, ki ≥ 0 for i = 1, 2, 3.

(1)

i =1

For any two distinct nonnegative integer solutions k1 , k2 , k3 and k1 , k2 , k3 of Diophantine equation (1), we

denote by J 14k+9 and J 24k+9 the dumbbell-MPGs obtained from J 9 by implementing ki and ki dumbbell transformations in C i respectively, where i = 1, 2, 3. By the deﬁnition of dumbbell transformation, we know that in J 14k+9 the distance of two vertices of degree 4 in C i and C j is

ki + k j + 2 and in J 24k+9 is ki + kj + 2, where i , j ∈ {1, 2, 3} and i = j. Since {k1 , k2 , k3 } = {k1 , k2 , k3 } and

3

i =1 k i

3

=

i =1 k i = k, there exist i , j , ∈ {1, 2, 3} such that k i + k j = ki + k j and ki + k = ki + k , where {i , j , } = {1, 2, 3}. Thus,

J 14k+9 and J 24k+9 are not isomorphic. It follows that tk is equal to the number of unordered partitions of k into 3 parts with each part ≥ 0. By Lemma 2.4, tk is equal to the number of unordered partitions of k such that each part is at most 3 and at least 0, that is, tk is equal to the number ofnonnegative integer 3 solutions of Diophantine equation i =1 ixi = n. There-

fore, by Lemma 2.3, tk = A (k, 3) = 2 9

cos

2kπ 3

.

2

(k+3)2 12

−

7 72

+

(−1)k 8

+

3. A stronger conjecture on purely tree-4-colorable MPGs Let G be an MPG with a separating cycle C . We denote by Int(C ) the subgraph of G consisting of C and its interior and by Ext(C ) the subgraph of G consisting of C and its exterior. Obviously, both Int(C ) and Ext(C ) are MPGs. The proof of the following theorem is straightforward. Theorem 3.1. Let G be an MPG with a separating triangle C . Then G is purely tree-4-colorable if and only if both Int(C ) and Ext(C ) are purely tree-4-colorable. For 4-connected MPGs, we only found that the icosahedron and dumbbell-MPGs are purely tree-4-colorable. This prompts us to propose the following conjecture. Conjecture 3.2. Let G be a 4-connected MPG. Then G is purely tree-4-colorable if and only if G is the icosahedron or a dumbbell-MPG.

536

J. Xu et al. / Information Processing Letters 116 (2016) 532–536

Theorem 3.3. Conjecture 3.2 implies Conjecture 1.3. Proof. Suppose that Conjecture 3.2 is true. If G is a recursive MPG, then G is obviously uniquely 4-colorable. By Conjecture 3.2 and Theorem 2.2, any MPG G is not uniquely 4-colorable when G is 4-connected. Now we assume that G has separating 3-cycles. If δ(G ) ≥ 4. Let C be a separating 3-cycle of G such that the order of Int(C ) is as small as possible. Then Int (C ) has neither vertex of degree 3 nor separating 3-cycle. So Int(C ) is 4-connected. By Conjecture 3.2, Int(G ) is not uniquely 4-colorable. Therefore, G is not uniquely 4-colorable. If δ(G ) = 3. Deleting the vertices of degree 3 in G continuously, we can obtain a subgraph G of G such that δ(G ) ≥ 4 or | V (G )| = 4. If δ(G ) ≥ 4, then G is not uniquely 4-colorable by Conjecture 3.2. Note that each 4-coloring of G can be extended to a 4-coloring of G, so G is not uniquely 4-colorable. If | V (G )| = 4, then G is a recursive MPG. This completes the proof. 2 4. Remark In this paper, we mainly discuss purely tree-4-colorable planar graphs. For a purely tree-k-colorable planar graph, if k = 1, then G is trivial. If k = 2, it is easy to check that G is a nontrivial tree. When k = 3, we propose the following problem. Problem 4.1. Characterize purely tree-3-colorable planar graphs. Moreover, we obtain a property of purely tree-3-colorable planar graphs. Theorem 4.2. Every purely tree-3-colorable planar graph with at least 4 vertices has two 3-faces. Proof. Suppose that their exists a purely tree-3-colorable planar graph G which has at least 4 vertices and at most one 3-face. Now we prove that | E (G )| ≥ 2| F (G )|. If G has no 3-face, that is, d G ( f ) ≥ 4 for any face f ∈ F (G ). Then 2| E (G )| = f ∈ F (G ) d G ( f ) ≥ 4| F ( G )|, i.e., | E (G )| ≥ 2| F (G )|. If G has exactly one 3-face f 0 , since f ∈ F (G ) d G ( f ) = 2| E (G )| is an even number, there exists a k-face f 1

in G for some odd number k ≥5. Hence, 2| E (G )| = f ∈ F (G ) d G ( f ) = d G ( f 0 ) + d G ( f 1 ) + f ∈ F (G ) { f 0 , f 1 } d G ( f ) ≥ 3 + 5 + 4(| F (G )| − 2) = 4| F (G )|, namely | E (G )| ≥ 2| F (G )|. Since | V (G )| + | F (G )| − | E (G )| = 2 by Euler’s Formula, we have | E (G )| ≤ 2| V (G )| − 4. On the other hand, we can obtain | E (G )| = 2| V (G )| − 3 by Lemma 1.4, a contradiction. 2 Acknowledgements This work is supported by 973 Program of China (No. 2013CB329600) and National Natural Science Foundation of China (Nos. 61372191, 61472012, 61472433, 61572046, 61502012, 61572492 and 61572153). References [1] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008. [2] F.D. Chartwright, F. Harary, On the coloring of signed graphs, Elem. Math. 23 (1968) 85–89. [3] S. Fiorini, On the chromatic index of a graph, III: uniquely edgecolorable graphs, Q. J. Math. (Oxford) 26 (3) (1975) 129–140. [4] S. Fiorini, R.J. Wilson, Edge colouring of graphs, Res. Notes Math. 16 (1977). [5] S. Fiorini, R.J. Wilson, Edge colourings of graphs, in: Selected Topics in Graph Theory, Academic Press, New York, 1978, pp. 103–126. [6] S. Fisk, Geometric coloring theory, Adv. Math. 24 (1977) 298–340. [7] T. Fowler, Unique coloring of planar graphs, Ph.D. Thesis, Georgia Institute of Technology, 1998. [8] T.C. Gleason, D. Cartwright, A note on a matrix criterion for unique colorability of asigned graph, Psychometrika 32 (1967) 291–296. [9] J.L. Goldwasser, C.Q. Zhang, On the minimal counterexamples to a conjecture about unique edge-3-coloring, Congr. Numer. 113 (1996) 143–152. [10] J.L. Goldwasser, C.Q. Zhang, Uniquely edge-colorable graphs and snarks, Graphs Comb. 16 (2000) 257–267. [11] D. Greenwell, H.V. Kronk, Uniquely line-colorable graphs, Can. Math. Bull. 16 (1973) 525–529. [12] L.G. Hua, Introduction to Number Theory, Science Press, Beijing, 1957, pp. 12–13 (in Chinese). [13] N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, The four-colour theorem, J. Comb. Theory, Ser. B 70 (1) (1997) 2–44. [14] A.G. Thomason, Hamiltonian cycles and uniquely edge colorable graphs, Ann. Discrete Math. 3 (1978) 259–268. [15] A.G. Thomason, Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable, J. Graph Theory 6 (1982) 219–221. [16] S.C. Xu, Tow maximal planar graphs with path bichromatic subgraph only, J. Cent. Univ. Natl. Nat. Sci. Ed. 14 (1) (2005) 5–9. [17] B. Grünbaum, Acyclic colorings of planar graphs, Isr. J. Math. 14 (1973) 390–408. [18] C.Q. Zhang, Hamiltonian weights and unique edge-3-colorings of cubic graphs, J. Graph Theory 20 (1995) 91–99.