(IJCNS) International Journal of Computer and Network Security, 75

Vol. 2, No. 5, May 2010

Coloring of Triangle Free Girth Graphs with

Minimal k-Colors
Dr. Mohammad Malkawi1 and Dr. Mohammad Al-Hajj Hasan2
1
Middle East University, Amman, Jordan, [email protected]
2
Middle East University, Amman, Jordan [email protected]

Abstract: It is known that there exist triangle free graphs with that, while the number of colors grows linearly, the number
arbitrary high chromatic number. A recursive construction of of nodes grows exponentially. Just like any other graph,
such graphs was first described by Blanches Descrates and girth-base graphs once constructed are difficult to color with
Mycielski. They have shown that for any positive integer k, there the minimum number of colors, especially when the number
exists a k-chromatic graph containing no triangle. In this paper, of nodes is relatively large.
we introduce an algorithm which detects the chromatic number
of an arbitrarily large girth-base graph and assigns colors to its
Lemma 1: If a graph is a Girth-g triangle free graph with n
nodes using the minimal number of colors, namely with exactly
k colors.. The algorithm complexity is O(Lg(n)), where n is the
nodes, then there exists a k-coloring of the graph, where k =
number of nodes of the graph. lg [(n+1)/3] + 2

Keywords: Graphs, Graph Girth, Graph Coloring, Chromatic

Number, Triangle-Free Graphs, Coloring Algorithm.

1. Introduction
There exist triangle free graphs with arbitrary high v1
chromatic number [4,5,6,7]. A recursive construction of g- v2
girth graphs is described in [1,2,3]. Blanches Descrates and
Mycielski have shown that for any positive integer k, there v5
exists a k-chromatic graph containing no triangle [9]. In this v3
paper, we will introduce an algorithm, which colors such
graphs with exactly k colors. First, we show how the k- v4
chromatic graphs are constructed using girth graphs.
A girth g-graph is a triangle free graph with the
shortest cycle containing g nodes. Blanches Descrates and Level 0, Girth 5, 3 Colors Graph
Mycielski [9] showed how to construct a k-chromatic graph
using a 5-girth graph (Figure 1, level 0).
v1
Call the original 5-node graph a level (0) graph. Add 6
new nodes to the graph (u1, u 2, u 3, u 4, u 5) and u.
Connect node ui to the neighbors of node vi . Obviously u1 v2
nodes ui and vi can be colored with the same color, since
they are not interconnected. Now connect u to (u1, u 2, u 3,
v5 u5 u2
u 4, u 5). Node u must be colored with a new color. The
resulting graph is the Grötzch graph with 11 nodes, no u
triangles, girth 4, and exactly 4 colors. Call this graph a
level (1) graph. In the same manner, we can construct a 5-
chromatic graph from the 11-node Grötzch graph. We add
u4 u3
12 new nodes (11+1). We connect each of the newly added
11 nodes to the neighbors of one and only one of the nodes v3
in the original 11-node graph. The newly added nodes will
be colored with the same colors as the original 11 nodes. v4
The 12th node connects to the newly added 11 nodes and
requires a new color. The total number of colors used is 5
colors. Call this graph a level (2) graph. By repeating this
Level 1, 4 Colors Graph
process, we can obtain a triangle free graph with any
chromatic number k= 3+i, where (i) is the level of the Figure 1: Girth g Graph Construction and Coloring
graph.

The number of nodes in a graph constructed in this

manner is n = (5*2i)+( 2i) – 1 = 6*2i– 1 = 3*2k-2– 1. Note
76 (IJCNS) International Journal of Computer and Network Security,
Vol. 2, No. 5, May 2010

The idea behind the algorithm was first observed when

constructing an exam scheduling algorithm with special
constraints [8].
This paper introduces an algorithm which detects the Theorem 1: Algorithm “Color Girth triangle Free Graphs”
chromatic number of an arbitrarily large girth-base graph will color all k-chromatic girth-g graphs with exactly k
and assigns colors to its nodes using the minimal number of colors.
colors. The algorithm complexity is O(Lg(n)). A formal First, we will show an example of how the algorithm can
definition of the algorithm is provided in the next section. color the constructed graphs with minimal number of colors.
The example will provide a ground for proof by induction.
We will also provide a formal proof for the theorem.
2. Coloring of k-chromatic Girth Graphs Example 1: Consider a level 2, 5-chromatic girth-4 graph.
The number of nodes in the graph is 23. The graph is
2.1 Algorithm Color Girth Triangle Free Graphs
illustrated in a matrix format in Table 1. For this graph the
Step 1: Sort the nodes in the graph based on the degree of
chromatic number is k=lg[(23+1)/3]+2 = 3+2 = 5.
the nodes (largest first)
The graph is initially constructed with nodes 1-5 (level 0).
Step 2:
At level 1, nodes 6-10 are added; node 6 connects to
• Select the first node in the list
neighbors of 1, node 7 connects to neighbors of 2, and so
• Color the node with the smallest available color (color 1 on. Then node 11 is added and connected to nodes 6-10. At
for the first node) level 2, we add nodes 12-22. Node 12 connects to neighbors
• Check the neighbors of this node; Color all the of nodes 1 through 11 respectively. Then node 23 is added
uncolored nodes in the list of neighbors and connected to nodes 12-22. The degree of each node is
• Move to the next node in the main list shown in the table.
Step 3: Repeat Step 2 until all nodes are colored

highest degree of 10) is the last node added at level 1. Let’s

Sort the nodes in descending order based on the nodes call nodes 23 and 11 the roots of level 2 and 1 respectively.
degree. Note that node 23 (with the highest degree of 11) is According to the algorithm, we start with node 23. We color
the last node added at level 2 and node 11 (with the next node 23 with the first available color, say the red color.
 (IJCNS) International Journal of Computer and Network Security, 77
Vol. 2, No. 5, May 2010

Node 23 has 11 neighbors. All the neighbors can be colored c. 3rd stage: 3 nodes (23+1/8). Number of colors is 1
with the same color, since by definition they are not d. 4th and 5th stages: 2 nodes. Number of colors is 1
interconnected with each other. So we color nodes 12-22 2. The total number of steps required to color the graph is
with blue. The number of nodes colored at this step is 5 = Lg 23
(1+11) = 12. Actually this is equal to the number of nodes
added at level 2, i.e., (N+1)/2.
2.2 Proof:
We now present a formal proof of the theorem. By
Next we move down the list to the root node at level 1,
construction, a girth graph consists of two major parts; the
i.e., node 11 with degree 10. By definition, node 11 is not
foundation, which is the 5-node cycle, and a multi-level
connected to node 23. Thus it may reuse the red color. Half
structure of nodes. Each level adds twice the number of
of the neighbors of node 11 are also neighbors of node 23
nodes to the previous level plus one root. The root at each
since they were added at the second level, and thus they
level is connected only to the newly added nodes, and is
must have been colored at the previous step with the blue
isolated from all the nodes added at the previous level(s).
color (nodes 19-22). The other half (nodes 6-10) were added
The largest degree node is the root of the last level in the
at level 1. Each of these nodes is connected to at least one of
graph. The degree of this node is d=(N-1)/2. The next
the nodes that have been colored at the previous step. A new
largest degree node is the root of the next level down, with
color, say color green, is required to color nodes 6-10. Note
degree = d-1, and so on.
that nodes 6-10 are not connected within each other, so they
The algorithm sorts the nodes of the graph in a
all can use the same color. At the end of this step, all nodes
descending order based on the degree of nodes. By
added at level one (5+1) are colored, and only one new color
definition, the largest degree node is the root of the last
is added.
(highest) level.
Assume that we construct a girth graph with (i) levels.
The next node in the list is node 5. Note that at this
For (i=0), the graph has 5 nodes. For (i=1), the graph has 11
stage, we have arrived at the original 5 nodes cycle (1
nodes. For (i=5), the graph has 191 nodes. At the (ith) level,
through 5). All of these nodes have the same degree. So we
the number of nodes is N=(5*2i)+( 2i)-1. The node with the
can start with any of them and get the same result. Node 5
largest degree is the last node added to the graph, i.e., the
has 8 neighbors. 6 out of 8 nodes have already been colored
root at level (i) and is connected to (N-1)/2-1 nodes; so the
with colors green and blue. Node 5 can take the color red.
degree at level (i) di = (3*2i-1). The next largest degree node
Note that color red is only used by the root nodes (11 and
is the root node added at the previous level (i-1). This node
23) at levels 1 and 2. These nodes do not connect to any of
is connected to nodes at the current level (i-1) and nodes at
the inner most 5-nodes cycle. The neighbors of 5 (nodes 1
the upper level (i). The number of nodes connected at the
and 4) require a new color, say the yellow color. The total
current level (i-1) = (3*2i-1-1). The number of nodes
number of nodes colored at this stage is (2+1). It is worth
connected to the root at the upper level (i) is = (3*2i-1-1). So
noting that the inner 5-node cycle requires at most 3 colors.
the degree at level (i-1), di-1 =2*(3*2i-1-1) = 3*2i-2. The
One of the already used colors can certainly be reused. This
next largest degree node is the root at level (i-2). The root is
is the color given to the root nodes added at each of the
connected to (3*2i-2-1) nodes at level (i-2). It is connected to
subsequent levels of the graph construction. So, when the
same number of nodes at level (i-1). It is also connected to
algorithm reaches the last 5 nodes in the graph, only 2 new
2*(3*2i-2-1) at level (i). So the degree at level (i-2) di-2 =
colors will be required.
(3*2i-2-1) + (3*2i-2-1) + 2*(3*2i-2-1) = (3*2i-2-1)*22. In
The next node in the list is node 1. Node 1 has already been
general, the degree of a root node at level (i-k), where k =
colored with the yellow color. All the neighbors of node 1
0,1, 2, … (i-2) is given by di-k= (3*2i-k-1)* 2k.
have been colored except for node 2, which can take the
For example, let (i=5). The total number of nodes in
color red. The next node in the list is node 2. Node 2 has
the graph is (6*25-1) = 191. d5= (3*25-1) = 95; d4= 2*(3*24-
already been colored. All of its neighbors are colored except
1) = 94; d3= 22*(3*23-1) = 92; d2= 23*(3*22-1) = 88.
for node 3. Node 3 requires a new color, say the color pink.
The algorithm sorts the nodes based on node degrees
in a descending order. Thus, the algorithm will color the
At this stage all the nodes of the graph have been
nodes starting with the roots at each level.
colored with five colors, and the algorithm terminates. The
At level (i), the algorithm will color the root node and
termination criterion of the algorithm is simple. The
all its adjacent nodes. Since the adjacent nodes are not
algorithm maintains a list of all the nodes that have not been
interconnected, they can assume the same color. The root
colored. Every time a node is colored, the node will be
will have a different color. So step one, will consume two
removed from the list. The algorithm terminates when the
colors. The next step will take care of the nodes at the next
list becomes empty.
lower level. Since the root at this level is not connected to
We observe the followings from the process of coloring the
the root at the upper level, it can assume the color of the
graph.
root at the upper level; so no new color is consumed. The
1. The number of nodes and colors covered at each stage
neighbors of the root at this level are split in two sets. One
are as follows:
set belongs to the upper level, so this set has already been
a. First stage: 12 nodes = ((23+1)/2). Number of colors
colored. The second set is not inter-connected, so the nodes
used is 2
of this set can all be colored with the same color. A new
b. 2nd stage: 6 nodes = ((23+1)/4). Number of colors is
color will be consumed. Similarly, at the next level, the root
1
78 (IJCNS) International Journal of Computer and Network Security,
Vol. 2, No. 5, May 2010

can assume the same colors of the previous roots, since they
are not interconnected. The neighbors of this node are split Authors Profile
in 3 sets. Two sets belong to the upper 2 levels and one set Dr. Mohammad Malkawi received his
belongs to the current level. The nodes, which belong to the Ph.D. degree in computer engineering
upper 2 levels, have been colored at the previous steps. The from the University of Illinois at Urbana-
nodes in the current level are not interconnected, so they can Champaign in 1986. He received his BS
assume one color. Continuing in this manner, the algorithm and MS in computer engineering in 1980
and 1983. He was a member of the High
will consume one color at each level until it reaches the
Productivity Computing Systems team at
lowest 5 nodes in the graph, where it will consume 2 new SUN Microsystems, and the high availability platform team at
colors. Motorola. Currently, he is associate professor at Middle East
Thus, the algorithm detects the structure of the graph University in Jordan.
and colors the nodes with the minimal number of
Mohammad M Al-Haj Hassan obtained
colors 2 + ∑1 . The algorithm also uses minimum number
i +1
his B.Sc. and Master degrees from The
University of Jordan in 1973 and 1977
of steps because it colors the roots and their neighbors first. respectively, and his Ph.D. degree in
Computer Science from Clarkson
University at NY / USA. His main field
3. Conclusions of Specialization is Computer Algorithms
This paper presents a coloring algorithm which colors with specific concentration on Graph
a girth-g, triangle free graphs with arbitrarily large k- Algorithms & Their Applications. Other
chromatic number. The algorithm detects the structure of a fields of research are: Machine Learning,
girth-g graph and colors the graph with exactly k colors. Parallel Computations and Algorithms,
The algorithm terminates in O(Lg(n)) steps. Distance Learning and Web-Based Courses Design. Professor M.
Al-Haj Hassan was the Dean of several Faculties in several
universities. He is a member in the Editorial Board and/or referee
of several journals. He has been the Secretary General of The
International Arab Conference on Information Technology (ACIT)
References
for 4 years. Currently, he is a professor of Computer Science and
[1] Bollobas,B., Sauer,N.: ”Uniquely Colorable Graphs
the Vice President at Middle East University in Jordan.
with Large Girth,” Canad. J. Math. 28 (1976), no.
6, 1340-1344.
[2] Emden-Weinert,T., Hougardy,S., Kreuter,B.:
”Uniquely Colorable Graphs and the Hardness of
Coloring Graphs of Large Girth,” Com-bin.
Probab. Comput. 7 (1998), no. 4, 375-386.
[3] Erdos,P.: ”Graph Theory and Probability,” Canad.
J. Math 11 (1959), 34-38.
[4] Muller,V.: ”On Colorings of Graphs Without Short
Cycles,” Discrete Mathematics 26 (1979), 165-176.
[5] Nesetril,J., Zhu,X.: ”Construction of Sparse Graphs
with Prescribed Circular Colorings,” Discrete
Mathematics 233 (2001), 277-291.
[6] Steffen,E., Zhu,X.: ”Star Chromatic Numbers of
Graphs,” Combinatoria 16 (1996), no. 3, 439-448.
[7] Zhu,X.: ”Uniquely H-colorable Graphs with Large
Girth”, J. Graph Theory 23 (1996), no. 1, 33-41.
[8] Mohammad Malkawi, Mohammad Al-Haj Hassan,
and Osama Al-Haj Hassan, “A New Exam
Scheduling Algorithm Using Graph Coloring”, The
International Arab Journal of Information
Technology, Vol. 5, No. 1, 2008; pp. 80-86.
[9] Soifer, Alexander “Mathematics of Coloring and
the Colorful Life of its Creators”, Springer; pp, 83-
86; ISBN: 978-0-387-74640-1