# The Relation between Centre Folding of Graph and its Chromatic Number

^{*}

**Corresponding Author:**Rafat H, Mathematics Department, Faculty of Science, Tanta University, Tanta, Egypt, Tel: 3313619, Email: [email protected]

*
Received Date: Sep 19, 2017 /
Accepted Date: Oct 13, 2017 /
Published Date: Oct 27, 2017 *

### Abstract

Coloring graph is a good branch in graph theory and has a lot of application in our life. So, in this paper we have defined a new type of folding. Also, we have found strong relations between this folding of graph and its chromatic number. Theorems governing the relations to be obtained. Traffic lights problem here was solved.

**Keywords:**
Folding; Graph; Vertex-coloring; Chromatic number

**2010 Mathematics subject classification:** 05C15; 05C99; 05C90; 05C30

#### Introduction

The authors introduced the main idea of folding on manifolds and studied the stratification determined by the folds or singularities [1,2]. The authors [3-7] reviewed various folding problems arising in the physics of membranes and polymers. These problems are found to be related to coloring problems. Nešetril and De Mendez [8] defined folding of a directed graph as a coloring. While in general folding is as complicated as homomorphisms for some classes they present useful tool to study colorings and homomorphisms.

Let G be a graph and *m* be a positive integer, a m-coloring is a function M: V (G)→{1, . . . , m} from the set of vertex into the positive integers set less than or equal to m [9]. We say that M is a proper m-coloring of G if for every pair u, v of adjacent vertices, M(u) ≠M(v) that is, the adjacent vertices are colored differently. If such a coloring exists for a graph G, we say that G is m-colorable. Given a graph G. The chromatic number of G, denoted by ÷(*G*) is the minimum value of m such that G admits a m-coloring. That is, ÷(*G*) is the smallest number of colors needed to color the vertices of G in such a way that adjacent vertices are colored by different colors.

The above discussion motivates us to define new type of folding of a simple graph to calculate the chromatic number by easy way.

#### The Main Results

In this article we have defined a new type of folding of graph called centre folding. But, at first we defined the following definitions:

**Definition 1**

In any graph G a vertex v_{i} is * an n-pure neighbour* of the vertex v

_{j}if the shortest length of path between them is n, where n is integer and n ≥ 1.

**Definition 2**

Any vertex v_{i} in a graph G is called centre n-pure neighbour if it has one or more than one n-pure neighbour vertex.

As shown from **Figure 1** the graph G has a lot of vertices are centre 2-pure neighbours, for example v_{2} is centre 2-pure neighbour for the vertices v_{4}, v_{6} and v_{7}.

**Definition 3**

A centre folding F of a graph G is a map form G to another one G^{∗} fold any vertex to it's centre 2-Pure neighbour, such that any two adjacent vertices have the same centre 2-pure neighbour one of them be folded to this centre and the other to itself like others.

*Now we will discuss the relations between centre folding of a simple graph and its chromatic numbers:*

Consider the graph G in **Figure 1**, it's obvious that the chromatic number of G is 3, i.e., ÷(*G*) = 3 , and it's order is 7 . Since the vertex v_{1} is centre 2-pure neighbours of the vertices v_{3} and v_{5} . Then we can defined a centre folding map F_{1}: G → G_{1}, such that F_{1}(v_{3}) =v_{1}, F_{1}(v_{5})=v_{1} and F_{1}(v_{i}) =v_{i}, i∈{1,2,4,6,7} (**Figure 2**).

The adjacent matrices of G and G_{1} are given by

From **Figure 2** we noticed that the chromatic number of G_{1} is ÷ (*G*_{1}) = 3, and its order is 5.

Since the vertex v_{6 is} centre 2-pure neighbour of the vertices v_{2} and v_{4}. Then a centre folding map

F_{2}: G_{1} → G_{2}, such that F_{2}(v_{2})=v_{6}, F_{2}(v_{4})=v_{6} and F_{2}(v_{i}) =v_{i}, i∈{1,6,7} (**Figure 3**).

The adjacent matrices corresponding graphs in **Figure 3** are

It is clear from **Figure 3** that the graph G_{2} is complete graph, i.e., the chromatic number of it equal to its order. Also, we cannot define a centre folding on G_{2} i.e., F_{2} is the end of centre folding of G.

From the above discussion we deduce the following results:

**Proposition 1**

The end of centre folding of a connected graph is complete graph.

**Proof**

Let a graph G^{∗} be the end of canter folding of a connected graph G and let G^{∗} be not complete graph. Since G^{∗} is the end of canter folding of G then G^{∗} has not any vertex is centred 2-pure neighbour to another one, i.e., every vertex in G^{∗} is connected to the others. That is contradiction. Hence G^{∗} is complete graph.

**Proposition 2**

If any vertex in a graph G is folded by centre folding to another one then these two vertices have the same color.

** Theorem 1 **

If any connected graph cannot be folded by centre folding then the chromatic number of this graph equal to its order.

**Proof**

Let we have a connected graph G and let G cannot be folded by centre folding. Then this graph has not any vertex is 2-pure neighbour to another one, i.e., every vertex is connected to the others. Hence this graph is complete graph. So, the chromatic number of it equals to its order.

**Theorem 2**

If any disconnected graph cannot be folded by centre folding then the chromatic number of this graph

, Where n is the size of the graph

**Proof**

Let we have a disconnected graph G and let G cannot be folded by centre folding. Then this graph has not any vertex is 2-pure neighbour to another one. Then this graph is one of these cases:

**Case 1:** The graph is null graph. Hence its chromatic number equal one.

**Case 2:** The graph is the union of two or more graphs one is null and the other is complete or all complete. Then the chromatic number of our graph equal to the chromatic number of the biggest one which its chromatic number equal its order where n is the size. Hence the chromatic number of our graph

**Theorem 3**

The chromatic number of connected graph G equal to the order of the graph after the end of centre folding of *G*.

**Proof**

Let *G* be a connected graph and G can be folded by centre folding. Then this graph has at least vertex is 2-pure neighbour to one or more than one vertex. Then from proposition 2 these vertices have the same color. Since end of centre folding of a connected graph is complete graph (proposition 1), then the chromatic number of the connected graph G equal to the chromatic number of complete graph which equal its order.

**Theorem 4**

The chromatic number of disconnected graph equal to the order of biggest component of it after end of center folding.

**Proof**

Let G be a disconnected graph G, this mean that this graph consisting more than one component. Then from proposition 1 the components of G at the end of centre folding of it are complete. Then the chromatic number of G equal to the chromatic number of biggest one, hence chromatic number of disconnected graph equal to the order of biggest component of it after end of centre folding.

#### Application

As we know traffic lights is the most common application of coloring in our life. As shown from **Figure 4** there are 10 traffic lanes, T_{1} to T_{10}. The system of the traffic light consists of a certain number of phases and at any phase, vehicles in lanes for which the light is green may proceed safely through the intersection and any lane is broad enough for only one vehicle at a time. Now we want to calculate the minimum number of phases needed for the traffic light system such that all vehicles may proceed safely through the intersection.

Let us solve the problem above by drawing the graph of it, to model the situation (**Figure 5**).

From **Figure 5** we can defined the centre folding F_{1}: G → G_{1}, such that F_{1}(L_{5})=L_{1}, F_{1}(L_{6})=L_{1} and F_{1}(L_{10}) =L_{1}, F_{1}(L_{i})=L_{i} i∈{1,2,3,7,9}. After we can defined another centre folding F_{2}: G_{1} → G_{2}, such that F_{2}(L_{8})=L_{9}, F_{2}(L_{4})=L_{3},F_{2}(L_{i}) ,i∈{1,2,3,7,} **Figure 6**.

It is clear that the minimum number of phases we need for the traffic light system is three where the first phase contain { L_{5}, L_{6}, L_{10}, L_{1}}, the second phase contain { L_{7}, L_{8}, L_{9}, L_{2}} and the third phase contain {L_{3}, L_{4}}.

#### References

- Robertson SA (1978) Isometric folding of Riemannian manifolds. Proceeding of the Royal 79: 275-284.
- Bondy A, Murty MR (2008) Graph Theory. Graduate Texts in Mathematics series.
- Borodin OV (2013) Colorings of plane graphs. Discrete Mathematics 313: 315-539.
- Demange M, Ekim T, Ries B, Tanasescu C (2015) On some applications of the selective graph coloring problem. European Journal of Operational Research 240: 307-314.
- Di-Francesco P (2000) Folding and coloring problem in mathematics and physics. Bulletin of the American Mathematics Society 37: 251-307.
- El-Ghoul M, Salama F, Pelila AS (2012) Folding of 2-Tangle-Graphs. Journal of Mathematics Research Canadian Centre of Science and Education 4: 86-100.
- Molloy M, Reed B (2014) Colouring graphs when the number of colours is almost the maximum degree. Journal of Combinatorial Theory Series B Elsevier, pp: 134-195.
- Nešetrila J, De Mendez PO (2006) Folding. Journal al of Combinatorial Theory Series B Elsevier 96: 730-739.
- Tomon I (2015) On the chromatic number of regular graphs of matrix algebras. Linear Algebra and its Applications Elsevier 475: 154-162.

Citation: Rafat H (2017) The Relation between Centre Folding of Graph and its Chromatic Number. J Appl Computat Math 6: 378. Doi: 10.4172/2168-9679.1000378

Copyright: ©2017 Rafat H. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.