Printer Friendly

Relation between chromatic number and graph folding.

1. Introduction

The folding of a manifold was, firstly introduced by S. Robertson in 1977 [7]. While the unfolding of a manifold appeared in [2].Since them many authors have studied some types of folding of manifold such as in [3,5]. The folding of the graph defined by E. El-Kholy and A. El-Esawy [4]. Some application of the folding of a manifold discussed in [1].

2. Definitions

Definition 1 Let [G.sub.1] and [G.sub.2] be graphs and f: [G.sub.1] [right arrow] [G.sub.2], be a continuous function. Then f is called a graph map, if

(i) for each vertex v [member of] V ([G.sub.1]), f(v) is a vertex in V ([G.sub.2]),

(ii) for each edge e [member of] E ([G.sub.l]), dim (f(e))[less than or equal to]dim(e) [4]

Definition 2 A graph map f: [G.sub.1] [right arrow] [G.sub.2], is called a graph folding if and only if f maps vertices to vertices and edges to edges, i.e.,

(i) for each vertex v [member of] V ([G.sub.1]), f(v) is a vertex in V ([G.sub.2]),

(ii) for each e [member of] E ([G.sub.1]), f(e) is an edge in E ([G.sub.2]) [4]

Note that if the vertices of an edge e = (u,v) [member of] E ([G.sub.1]) are mapped to the same vertex, then the edge e will collapse to this vertex and hence we cannot get a graph folding. In other words any graph folding cannot map edges to loops but it may maps loops to loops

We will denote the set of graph folding between graphs [G.sub.1] and [G.sub.2] by [eta] ([G.sub.1], [G.sub.2]) and the set of graph folding of [G.sub.1] to itself by [eta] ([G.sub.1]). In this case of a graph folding f the set of singularities, [summation]f, consists of vertices only.

Definition 3 A graph folding f is called non-trivial if [summation] f [not equal to] [phi]. In this case no. V (f([G.sub.1]) < no. V (G x), also no. E (f([G.sub.1]) < no. E ([G.sub.1])

Definition 4 The chromatic number [gamma](G) of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color, i.e., the smallest value of k possible to obtain a k-coloring [6]

A graph with chromatic number two is said to be bicolorable, and a graph with chromatic number three is said to be three-colorable.

3. The main results

Theorem 1 For any connected graph G, if the chromatic number [gamma](G) equal to the number of vertices. Then G cannot be folded

Proof. For any connected graph G with n vertices, the chromatic number [gamma](G) satisfies 2[less than or equal to][gamma](G)[less than or equal to]n. If the chromatic number [gamma](G) equal the number of vertices n, i.e., we have n color and n vertices and since any vertex adjacent with another vertex have different color. Then any vertex of G will be connected with all other n - 1 vertices, so the graph G will be a complete graph [K.sub.n]. Hence we cannot define any non-trivial graph folding in [K.sub.n] because any non-trivial graph map f on the vertices of [K.sub.n] which map the vertex [v.sub.i] to the vertex [v.sub.j] will collapse the edge ([v.sub.i], [v.sub.j]) to a vertex. [v.sub.i]. Then f is not a graph folding.

Example 1 Let G be a graph with [gamma](G) = n = 5, then G is a complete graph [K.sub.5]. So any non-trivial graph map on the vertices of [K.sub.5] will collapse an edge to a vertex which is not a graph folding on [K.sub.5] see Fig (1)

[FIGURE 1 OMITTED]

Theorem 2 For any connected graph G, if the chromatic number [gamma](G) Equal two. Then G can be folded to an edge.

Proof. For any connected graph G, since 2[less than or equal to][gamma](G)[less than or equal to]n. If the chromatic number [gamma](G) equal two, i.e., we have two different color only for all vertices of G, so all adjacent vertices of any vertex will have the same color. Then we can divided all the vertices of G into two sets A and B each one have the same color and each vertex of A adjacent with vertices of B only, i.e., we have a bipartite graph. Then we can define a graph map f on G which maps a vertex to a vertex of the same color, so f maps a vertex of the set A to a vertex on A and a vertex of the set B to a vertex on B. Then any edge of G under f will mapped to an edge because each edge joined a vertex of A to a vertex of B hence f is a graph folding.

Example. 2 The star graph [S.sub.n]; n[greater than or equal to]2 have chromatic number [gamma](G) = 2, we define the graph map f: [S.sub.n] [right arrow] [S.sub.n] as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus the image of any edge of E(G) will be the edge ([v.sub.1], [v.sub.2])

[FIGURE 2 OMITTED]

Example. 3 Since any tree T have [gamma](T) = 2 so any tree can be folded into itself by a sequence of graph folding which maps any vertex to another vertex have the same color until we have an edge which have different color vertices

Definition 5 A cycle graph [C.sub.n], n > 1 have chromatic number

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Example. 4 Any cycle graph with [gamma]([C.sub.n]) = 2 (have even number of vertices) can be folded by dividing its vertices into two sets A and B each one have (the same color and half the number of vertices). In this case each vertex in A is adjacent to two vertices only of B. We define the folding map

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Fig (3) show the folding graph of [C.sub.6]

[FIGURE 3 OMITTED]

Theorem 3 Any cycle graph [C.sub.n] have chromatic number [gamma]([C.sub.n]) = 3 can be folded until we have a 3-cycle its vertices have different color.

Proof. If the chromatic number of cycle graph [C.sub.n] is three, i.e., [gamma]([C.sub.n]) = 3, it must contains an odd number of vertices which called an odd cycle. Since any graph with odd cycle can not be a bipartite graph [6]. So we can color the vertices of [C.sub.n] in such away that each edge have vertices of colors 1 and 2 except the last edge will have color 3 and 1. Then we can define a folding graph f: [C.sub.n] [right arrow] [C.sub.n] by mapping all vertices of the same color to one vertex of the same color. In the limit we have a 3-cycle each vertex have different color which can not be folded any more, since any other folding will collapse an edge to a vertex. Fig (4) shows folding for [C.sub.5], where the graph folding f can be define as follows

f([v.sub.1],[v.sub.2],[v.sub.3],[v.sub.4],[v.sub.5]) = ([v.sub.1],[v.sub.2],[v.sub.1],[v.sub.2],[v.sub.5]).

[FIGURE 4 OMITTED]

Definition 6 A wheel graph [W.sub.n] of order n, is a graph that contains a cycle of order n - 1, and for which every graph vertex in the cycle is connected to one other graph vertex which is known as the hub. The chromatic number of [W.sub.n] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 4 Any wheel graph have chromatic number [gamma]([W.sub.n]) = 3 can be folded into itself by a folding graph onto a triangle graph.

Proof. When the wheel graph have chromatic number [gamma]([W.sub.n]) = 3, so we have three colors for all the verities of [W.sub.n]. We must fixed one color for the hub vertex [v.sub.1] since the hub vertex adjacent to all other vertices of [W.sub.n], then this color cannot colors any other vertex. Also for [gamma]([W.sub.n]) = 3, the number of vertices n is odd so we have even cycle [C.sub.n-1]. Then we can color the vertices in [C.sub.n-1] alternatively by the remaining two colors, and the folding graph f: [W.sub.n] [right arrow] [W.sub.n] can be define as follows f ([v.sub.1], [v.sub.i], [v.sub.j]) = ([v.sub.1], [v.sub.2], [v.sub.3]) where i even number, j odd number. In the final we have a triangle graph each vertex have different color. Fig (5) shows folding of [W.sub.5]

[FIGURE 5 OMITTED]

Theorem 4 Any wheel graph have chromatic number [gamma]([W.sub.n]) = 4 can not be folded

Proof. If [gamma]([W.sub.n]) = 4, the number of colors is four one of them fixed for the hub vertex [v.sub.1] and the other three colors for the cycle [C.sub.n-1] which is odd cycle since n is even. We can color the vertices of [C.sub.n-1] alternatively by two colors from the three colors remaining until the last vertex in [C.sub.n-1] which must take the four color. In this case we cannot define a graph folding since the hub vertex cannot mapped to any vertex because this collapse the edge joining these two vertices to a vertex and since the boundary cycle [C.sub.n-1] contain an odd number of edges so we cannot map any vertex to another vertex of the same (different) color. Fig (6) show [W.sub.6] which cannot folded

[FIGURE 6 OMITTED]

Definition 7 A clique of a graph is its maximal complete subgraph. The number of graph vertices in the largest clique of G, is called the clique number [omega](G). [6]

Lemma 1 If the clique number of a graph G equal two, [omega](G) = 2. Then G can be folded

Proof. Since for a connected graph G, the chromatic number of a graph is equal to or greater than its clique number, i.e., 2[less than or equal to][omega](G)[less than or equal to][gamma](G)[less than or equal to]n. When 2 = [omega](G) = [gamma](G) we can define sequence of folding graphs on G until we have one edge with two different colors as in Theorem 2.

For example any tree or star graph or cubical graph and Heawood graph have [omega](G) = 2. So it can be folded to an edge.

Theorem 5 For any connected graph G, if 2 [less than or equal to] [omega](G) = [gamma] (G) = k [less than or equal to] n. We can define a sequence of folding on G until we have a clique of order k.

Proof. If 2[less than or equal to][omega](G) = [gamma](G) = k[less than or equal to]n so we have a clique of order k, i.e., we have k vertices connected to each other, so this vertices must take different colors from 1 to k and the other vertices on G which is not on the clique take any other colors such that any edge must take different colors of vertices. Then we can define a graph map which take a vertex to another vertex of the same color f: G [right arrow] G where f([v.sub.i]) = [v.sub.j], such that [v.sub.i], [v.sub.j] have the same color. This is a graph folding since any edge have different color of vertices. By repeating this process until we arrive to a clique of order k which cannot folded again, because all its vertices have different colors.

Example. 5 The octahedral graph G which have 6 vertices, 12 edges, 8 faces, in this case [omega](G) = [gamma](G) = 3[less than or equal to]n = 6. In this case there are three color for each clique (triangle), The graph map f can be define as follows f([v.sub.1], [v.sub.2], [v.sub.3], [v.sub.4], [v.sub.6]) = ([v.sub.1], [v.sub.2], [v.sub.3], [v.sub.1], [v.sub.2], [v.sub.3]) which take all vertices of the same color to one of them, it is clear that f is a graph folding, see Fig (7)

[FIGURE 7 OMITTED]

Theorem 6 For any connected graph G, if [omega](G)[not equal to][gamma](G), i.e., [omega](G) < [gamma](G). Then there is no non-trivial graph folding can be defined for G.

Proof. Since [omega](G)[less than or equal to][gamma](G), if the chromatic number equal the clique number [omega] (G) = [gamma](G), so in order to colors the vertices of G cyclically by the chromatic number, then we must have an even number of cliques. Conversely, if the clique number is less than the chromatic number [omega](G) < [gamma](G) then the number of the cliques in G must be odd number. Then we cannot define any nontrivial graph folding f: G [right arrow] G because any graph map f will map an edge of G to an edge does not belongs to G or collapse an edge to a vertex.

Example. 6 Let G be a Wheel graph [W.sub.8] with vertex set V([W.sub.8]) = {[v.sub.1], [v.sub.2],...,[v.sub.8]} such that the hub vertex is [v.sub.1]. [W.sub.8] have clique number [omega]([W.sub.8]) = 3 and its chromatic number [gamma]([W.sub.8]) = 4. One of the color must fixed for the hub vertex and the other colors for the cycle [C.sub.7]. In this case we have an odd number of clique (triangle) and any graph map f: [W.sub.8] [right arrow] [W.sub.8] define on the vertex set of [W.sub.8] as follows f{[v.sub.1],[v.sub.2],[v.sub.3],[v.sub.4],[v.sub.5],[v.sub.6],[v.sub.7],[v.sub.8]} = {[v.sub.1],[v.sub.2],[v.sub.3],[v.sub.4],[v.sub.5],[v.sub.6],[v.sub.5],[v.sub.3]} which map the edge f{([v.sub.7],[v.sub.8])} = ([v.sub.5],[v.sub.3]) [not member of] E(G) and this contradicts the assumption that f is a graph folding, see Fig (8).

[FIGURE 8 OMITTED]

4. References

[1] Di-Francesco, P.: Folding and coloring problem in mathematics and physics, Bulletin of the American Mathematics Society, 37 (2000), 251-307

[2] El-Ghoul, M.: Unfolding of Riemannian manifolds, Commun. Fac. Sci. Univ Ankara Series, 37 (1988), 1-4.

[3] El-Kholy, E. M., Basher, M. and Zeen El-Deen, M.R.: Perfect folding of the plane, Soochow J. Math., Vol. 32, No. 4, (2006) 521-532.

[4] El-Kholy, E. M. and El-Esawy, A.: Graph folding of some special graphs, J. Math. And Statis., I (1), Sci. Pub., (2005), 66-70.

[5] Farran, H. R., El-Kholy, E. M. and Robertson, S. A.: Folding a surfaces to a polygon, Geometriae, Dedicata, 33, pp. 255-266, Germany (1996)

[6] Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994

[7] Robertson, S. A.: Isometric folding of Riemannian manifolds, Proc. Roy. Soc Edinburgh 77 (1977), 275-289.

M. R. Zeen El-Deen

Department of Mathematics, Faculty of Science, Suez Canal University, Suez, Egypt E-mail: mrzd777@yahoo.com
COPYRIGHT 2010 Research India Publications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2010 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:El-Deen, M.R. Zeen
Publication:International Journal of Computational and Applied Mathematics
Date:Mar 1, 2010
Words:2670
Previous Article:Study of an exact solution of steady-state thermoelastic problem of a finite length hollow cylinder.
Next Article:Synchronization of an optical hyper-chaotic system.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters