Scribd
Upload
197 views

Term Paper

Branko Grunbaum introduced acyclic coloring and star coloring of graphs in the late 1970s. Acyclic coloring requires that every cycle uses at least 3 colors, resulting in a forest for 2-colored induced subgraphs. Star coloring prohibits paths of length 3 from being bicolored. The acyclic chromatic number is the minimum number of colors for an acyclic coloring, while the star chromatic number is the minimum for a star coloring. N. Ramya from Bharath University in India published a paper in 2014 on coloring corona graphs, specifically Cn ◉ K1,3 and Pn ◉ K2. The paper proved that the proper and acy

Uploaded by

Norshida Calibi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
197 views

Term Paper

Branko Grunbaum introduced acyclic coloring and star coloring of graphs in the late 1970s. Acyclic coloring requires that every cycle uses at least 3 colors, resulting in a forest for 2-colored induced subgraphs. Star coloring prohibits paths of length 3 from being bicolored. The acyclic chromatic number is the minimum number of colors for an acyclic coloring, while the star chromatic number is the minimum for a star coloring. N. Ramya from Bharath University in India published a paper in 2014 on coloring corona graphs, specifically Cn ◉ K1,3 and Pn ◉ K2. The paper proved that the proper and acy

Uploaded by

Norshida Calibi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

THE BACKGROUND OF THE STUDY

Branko Grunbaum during his late 1970s introduced the acyclic coloring and star
coloring of a graph. One generalization of star coloring is the closely related concept of acyclic
coloring, where it is required that every cycle uses at least three colors, so the two-color induced
subgraphs are forests. If we denote the acyclic chromatic number of a graph G by
have that

, we

, and in fact every star coloring of G is an acyclic coloring.

The star chromatic number has been proved to be bounded on every proper minor closed class
by Neetil & Ossona de Mendez on 2003. This result was further generalized by
Neetil & Ossona de Mendez on 2006 to all low-tree-depth colorings (standard coloring and
star coloring being low-tree-depth colorings with respective parameter 1 and 2).
N.Ramya from the Department of Mathematics of Bharath University in Selaiyur
,Chennai, India published a journal entitled On Coloring of Corona Graphs focusing on
corona of Cn K1,3. and a corona of Pn K2 through Indian Journal of Science and
Technology on March 2014.
DEFINITION OF TERMS

Let G be a graph. A labelling of the vertices of G such that no two neighbours in G are
assigned the same label is called a proper coloring of a graph G. Labelling or coloring of vertex x
isdenoted by (G).
Definition 1:
(Star coloring) A star coloring of a graph G is a proper coloring of G such that no path of

length 3 in G is bicolored. The star chromatic number of a graph G is denoted by s (G), the
smallest integer k for which G admits 3 star coloring with k colors.
Example : P4

Figure 1
G:

Definition 2 :
(Acyclic coloring) An acyclic coloring of a graph G is a proper coloring of G such that no
cyclein G is bicolored. The acyclic chromatic number a (G) of a graph G is the least
number of
colors needed in any acyclic coloring of G.
Figure 2
Example: C3
G:

.
RESULTS
Theorem (1):
The graph corona of Cn and K1, 3 Vn 3 (when n is odd) its proper coloring and acyclic
coloring are three.
Example:
When n is odd;

C4 K1,3:

The proper coloring (G) and acyclic coloring a(G) is 3.

Theorem (2):
The graph Corona of Cn and K1,3 V n 3, (n is an even) its chromatic number is 2, and
its acyclic chromatic number is 3. (ie) (G) < a (G).
Example:
When n is even:
C4 K1,3:

The proper coloring of C4 K1,3 is 2.


In Corona of C4 K1,3 proper coloring < acyclic coloring.

Theorem (3):
The graph Corona of Pn K2 which admits star coloring is 4 and acyclic coloring is 3.
Example
P4 K2 :

Thus the star coloring of P4 K2 is 4.

Thus the acyclic coloring of P4 K2 is 3.


REFERRENCE
1.Grunbaum B. Acyclic colorings of planar graphs. Isrel J Math. 1973; 14(3):390408.
2. Fertin G, Raspaud A, Reed B. Star coloring of graphs. J Graph Theory. 2004; 47(3):16382.
3. Kaladevi V, Kavitha G. Edge magic graceful labeling of some corona graphs. Proceedings of
ICMEB; 2012. p. 7779.
4. Ramya N, Rangarajan K, Sattanathan R. On rainbow coloring of some classes of graphs.
IJCA. 2012 May; 46(18): 3638.

ON COLORING ON CORONA GRAPHS


N.RAMYA

A Paper Presented to
Prof. Ricky F. Rulete
Bachelor of Science in Mathematics
University of Southeastern Philippines

Research Paper in Graph theory

Norshida A. Calibi
Bachelor of Science in Mathematis-3rd Year
March,2016

You might also like