The main problem in vertex coloring is how to color each vertex on a graph so that no two adjacent
vertices have the same color. Fractional coloring is a double coloring at vertices of different colors where the
adjacent vertices have different colors. In operations on the graph, one of them is known as amalgamation operation.
Amalgamation in the graph is divided into two, namely vertex amalgamation and side amalgamation. Coloring
vertex can be applied to the graph which is the result of the operation of some special graphs. Amalgamation
operation is to combine the vertices or sides of each graph to form a new graph. In this case, the resulting
amalgamation graph will produce the same fractional chromatic number with one of the fractional chromatic figures
of the graph prior to be amalgamated.
Published In:IJCSN Journal Volume 7, Issue 3
Date of Publication : June 2018
Pages : 158-165
Figures :--
Tables : 01
Junianto Sesa : Department of Mathematics, University of Hasanuddin, Makassar, South Sulawesi, Indonesia.
Armin Lawi : Department of Mathematics, University of Hasanuddin, Makassar, South Sulawesi, Indonesia.
Hasmawati : Department of Mathematics, University of Hasanuddin, Makassar, South Sulawesi, Indonesia.
Siswanto : Department of Statistics, Bogor Agricultural University, Bogor, West Java, Indonesia.
From the description or explanation above, the
researchers can conclude that fractional chromatic
numbers are very useful in the world of technology,
especially in the field of index code. The fractional
chromatic number of some graphs when combined
using an amalgamation operation will result in the
same as one chromatic fractional graph before the
operation.
[1] Aigner, M. and Ziegler, G. M. "The Chromatic
Number of Kneser Graphs.". New York: Springer-
Verlag, 2000.
[2] Anitha, R. and Lekshmi, R. S. "N-Sun
Decomposition of Complete, Complete Bipartite
and Some Harary Graphs." Int. J. Math., 2008.
[3] Bollobás, B. and Thomassen, A. "Set Colorourings
of Graphs." Disc. Math, 1979.
[4] Bryant, D. E. "Cycle Decompositions of Complete
Graphs." In Surveys in Combinatorics. Cambridge,
England: Cambridge University Press, 2007.
[5] Chartrand, G. Introductory Graph Theory. New
York: Dover, 1985.
[6] Diestel, R. Graph Theory. Graduate Texts in
Mathematics. 2005
[7] Edwards Katherine. Bounding the fractional
chromatic number of F?-free graphs. Department of
Computer Science Princeton University, Princeton,
NJ. 2013
[8] Ghosh, A.; Boyd, S.; and Saberi, A. "Minimizing
Effective Resistance of a Graph." Proc. 17th
Internat. Sympos. Math. Th. Network and Systems,
Kyoto, Japan, 2006.
[9] Godsil, C. and Royle, G. "Fractional Chromatic
Number." in Algebraic Graph Theory. New York:
Springer-Verlag, 2001.
[10] Golin, M. J. and Leung, Y. C. "Unhooking
Circulant Graphs: a Combinatorial Method for
Counting Spanning Trees and Other Parameters."
In Graph-Theoretic Concepts in Computer Science.
Revised Papers from the 30th International
Workshop WG, 2004
[11] Karthikeyan Shanmugam. 2013. Local Graph
Coloring and Index Coding. Department of
Mathematics and Computer Science the Open
University of Israel, Israel
[12] Larsen, M.; Propp, J.; and Ullman, D. "The
Fractional Chromatic Number of Mycielski's
Graphs." J. Graph, 1995
[13] Pardo G. Araujo; Diaz P. J. Carlos. “The (p,q)-
extremal problem and the fractional chromatic
number of Kneser hypergraphs.” Instituto de
Matem´aticas Universidad Nacional Aut´onoma de
M´exico Ciudad Universitaria, 2014
[14] Pirnazar, A. and Ullman, D. H. "Girth and
Fractional Chromatic Number of Planar Graphs." J.
Graph, 2002.
[15] Roberts, F. S. "On the Boxicity and Cubicity of a
Graph." In Recent Progress in Combinatorics. New
York: Academic Press, 1969.
[16] Saaty, T. L. and Kainen, P. C. The Four-Color
Problem: Assaults and Conquest. New York:
Dover, p. 148, 1986.
[17] Scheinerman, E. R. and Ullman, D. H. Fractional
Graph Theory A Rational Approach to the Theory
of Graphs. New York: Dover, 2011.
[18] Skiena, S. "Cycles, Stars, and Wheels."
in Implementing Discrete Mathematics:
Combinatorics and Graph Theory
with Mathematica. Reading, MA: Addison-Wesley,
1990.
[19] Young-Han Kim, and Fatemeh Arbabjolfaei.
Structural Properties of Index Coding Capacity
Using Fractional Graph Theory. University of
California, San Diego. 2015
[20] Zdenek Dvorak. Jean Sebastien and Sereni Jan
Volec. Subcubic triangle-free graphs have fractional
chromic number at most 14/5. 2013.
