Call For Papers
Contact Us

  Determination of Fractional Chromatic Number on Two Different Graphs of Amalgamation Operation  
  Authors : Junianto Sesa; Armin Lawi; Hasmawati; Siswanto
  Cite as:


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.


Amalgamation, Fractional Chromatic Number, Graph Coloring

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.