Determination of Fractional Chromatic Numbers in the Operation of Adding Two Different Graphs: Penentuan Bilangan Kromatik Fraksional pada Operasi Penjumlahan Dua Graf berbeda

Junianto Sesa; Siswanto Siswanto

doi:10.20956/j.v18i2.14501

Authors

Junianto Sesa Universitas Papua
Siswanto Siswanto Hasanuddin University https://orcid.org/0000-0003-1934-5343

DOI:

https://doi.org/10.20956/j.v18i2.14501

Keywords:

Graph, Fractional, Chromatic

Abstract

The development of graph theory has provided many new pieces of knowledge, one of them is graph color. Where the application is spread in various fields such as the coding index theory. Fractional coloring is multiple coloring at points with different colors where the adjoining point has a different color. The operation in the graph is known as the sum operation. Point coloring can be applied to graphs where the result of operations is from several special graphs. In this case, the graph summation results of the path graph and the cycle graph will produce the same fractional chromatic number as the sum of the fractional chromatic numbers of each graph before it is operated.

References

Chartrand G., 1985. Introductory Graph Theory. Dover, New York.

Godsil C., & Royle G., 2001. Fractional Chromatic Number. Springer Verlag, New York.

Bondy J A., 1978. A remark on two sufficient conditions for Hamilton cycles. Discrete Mathematics, Vol. 22, No. 2, 191-193.

Shanmugam K., Dimakis A G., & Langberg M., 2013. Local Graph Coloring and Index Coding. IEEE International Symposium on Information Theory, thn 2013, 1152-1156. Department of Mathematics and Computer Science the Open University of Israel, Israel.

Roberts F S., 1969. On the Boxicity and Cubicity of a Graph. Recent Progress in Combinatorics, Vol. 1, No. 1, 301-310.

Weisstein E W., 2011. Fractional Chromatic Number. https://mathworld. wolfram. com/. [11 Juni 2021].

Kainen P C., & Saaty T L., 1977. The Four-Color Problem: Assaults and Conquest. McGraw Hill, New York.

Pemmaraju S., & Skiena S., 2003. Cycles, Stars, and Wheels. Computational Discrete Mathematics Combinatiorics and Graph Theory in Mathematica, 249-284.

Larsen M., Propp J., & Ullman D., 1995. The Fractional Chromatic Number of Mycielski's Graphs. Journal of Graph Theory, Vol. 19, No. 3, 411-416.

Pirnazar A., & Ullman D H., 2002. Girth and Fractional Chromatic Number of Planar Graphs. Journal of Graph Theory, Vol. 39, No. 3, 201-217.

Golin M J., & Leung Y C., 2004. Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters. International Workshop on Graph-Theoretic Concepts in Computer Science, thn 2004, 296-307. Springer, Heidelberg, Berlin.

Ghosh A., Boyd S., & Saberi A., 2008. Minimizing Effective Resistance of a Graph. Proceeding 17th International Symposium Mathematics the Network and Systems, thn 2008, 37-66. Kyoto, Japan.

Bryant D., Cycle Decompositions of Complete Graphs. London Mathematical Society Lecture Note, 346, 67. Cambridge, England.

Anitha R., & Lekshmi R S., 2008. N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs. International Journal of Computational and Mathematical Sciences, Vol. 2, No. 1, 33-38.

Scheinerman E R., & Ullman D H., 2011. Fractional Graph Theory a Rational Approach to the Theory of Graphs. Dover, New York.

Edwards K., & King A D., 2013. Bounding the Fractional Chromatic Number of K_∆ Free Graphs. Siam Journal on Discrete Mathematics, Vol. 27, No. 2, 1184-1208.

Dvorak Z., Sereni J S., & Volec J., 2014. Subcubic Triangle-free Graphs have Fractional Chromatic Number at Most 14/5. Journal of the London Mathematical Society, Vol. 89, No. 3, 641-662.

Araujo-Pardo G., Diaz P J C., & Oliveros D., 2016. The (p, q)-extremal Problem and the Fractional Chromatic Number of Kneser Hypergraphs. Discrete Mathematics, Vol. 339, No. 11, 2819-2825.

Arbabjolfaei F., & Kim Y H., 2015. Structural Properties of Index Coding Capacity Using Fractional Graph Theory. IEEE International Symposium on Information Theory (ISIT), thn 2015, 1034-1038. University of California, San Diego.