﻿ The Relation between Centre Folding of Graph and its Chromatic Number
ISSN: 2168-9679

The Relation between Centre Folding of Graph and its Chromatic Number

Rafat H*
Mathematics Department, Faculty of Science, Tanta University, Tanta, Egypt
*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 vi is an n-pure neighbour of the vertex vj if the shortest length of path between them is n, where n is integer and n ≥ 1.

Definition 2

Any vertex vi 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 v2 is centre 2-pure neighbour for the vertices v4, v6 and v7.

Figure 1: n-pure neighbour.

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 v1 is centre 2-pure neighbours of the vertices v3 and v5 . Then we can defined a centre folding map F1: G → G1, such that F1(v3) =v1, F1(v5)=v1 and F1(vi) =vi, i∈{1,2,4,6,7} (Figure 2).

Figure 2: F1: G → G1, F1(v3)=v1, F1(v5)=v1.

The adjacent matrices of G and G1 are given by

From Figure 2 we noticed that the chromatic number of G1 is ÷ (G1) = 3, and its order is 5.

Since the vertex v6 is centre 2-pure neighbour of the vertices v2 and v4. Then a centre folding map

F2: G1 → G2, such that F2(v2)=v6, F2(v4)=v6 and F2(vi) =vi, i∈{1,6,7} (Figure 3).

Figure 3: F2: G1 → G2, F2(v2)=v6, F2(v4)=v6 and F2(vi)=vi, i∈{1,6,7}.

The adjacent matrices corresponding graphs in Figure 3 are

It is clear from Figure 3 that the graph G2 is complete graph, i.e., the chromatic number of it equal to its order. Also, we cannot define a centre folding on G2 i.e., F2 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, T1 to T10. 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.

Figure 4: Traffic light consists from T1 to T10.

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

Figure 5: F1: G → G1, such that F1(L5) =L1, F1(L6)=L1 and F1(L10) =L1, F1(Li) =Li i∈{1,2,3,7,9}.

From Figure 5 we can defined the centre folding F1: G → G1, such that F1(L5)=L1, F1(L6)=L1 and F1(L10) =L1, F1(Li)=Li i∈{1,2,3,7,9}. After we can defined another centre folding F2: G1 → G2, such that F2(L8)=L9, F2(L4)=L3,F2(Li) ,i∈{1,2,3,7,} Figure 6.

Figure 6: F2: G1 → G2, such that F2(L8)=L9, F2(L4)=L3,F2(Li) ,i∈{1,2,3,7,}.

It is clear that the minimum number of phases we need for the traffic light system is three where the first phase contain { L5, L6, L10, L1}, the second phase contain { L7, L8, L9, L2} and the third phase contain {L3, L4}.

References

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.

Select your language of interest to view the total content in your interested language

Recommended Journals
Viewmore
Article Usage
• Total views: 820
• [From(publication date): 0-2018 - Jan 23, 2019]
• Breakdown by view type
• HTML page views: 780