Year 2018, Volume 5 , Issue 1, Pages 19 - 27 2018-01-15

Coloring sums of extensions of certain graphs

Johan KOK [1] , Saptarshi BEJ [2]


We recall that the minimum number of colors that allow a proper coloring of graph $G$ is called the chromatic number of $G$ and denoted $\chi(G)$. Motivated by the introduction of the concept of the $b$-chromatic sum of a graph the concept of $\chi'$-chromatic sum and $\chi^+$-chromatic sum are introduced in this paper. The extended graph $G^x$ of a graph $G$ was recently introduced for certain regular graphs. This paper furthers the concepts of $\chi'$-chromatic sum and $\chi^+$-chromatic sum to extended paths and cycles. Bipartite graphs also receive some attention. The paper concludes with patterned structured graphs. These last said graphs are typically found in chemical and biological structures.
Chromatic number, $\chi'$-chromatic sum, $\chi^+$-chromatic sum, Extended path, Extended cycle
  • [1] A. Banerjee, S. Bej, On extension of regular graphs, arXiv:1509.05476v1 [math.CO].
  • [2] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
  • [3] S. Cabello, M. Jacovac, On the b–chromatic number of regular graphs, Discrete Appl. Math. 159 (2011) 1303–1310.
  • [4] G. Chartrand, L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
  • [5] J. T. Gross, J. Yellen, Graph Theory and Its Applications, CRC Press, 2006.
  • [6] J. E. Hopcroft, R. M. Karp, An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2(4) (1973) 225–231.
  • [7] J. Kok, N. K. Sudev, K. P. Chithra, Generalised colouring sums of graphs, Cogent Math. 3(1) (2016) 1–11.
  • [8] M. Kouider, A. El Sahili, About b–coloring of regular graphs, Rapport de Recherche, No. 1432, CNRS–Universite Paris Sud–LRI.
  • [9] E. Kubicka, A. J. Schwenk, An introduction to chromatic sums, Proc. ACM Computer Sci. Conf. (Louisville) (1989) 39–45.
  • [10] P. C. Lisna, M. S. Sunitha, b–chromatic sum of a graph, Discrete Math. Algorithm. Appl. 7(4) (2015) 1–15.
  • [11] N. K. Sudev, K. P. Chithra, J. Kok, Certain chromatic sums of some cycle-related graph classes, Discrete Math. Algorithm. Appl. 8(3) (2016) 1–25.
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0003-0106-1676
Author: Johan KOK

Author: Saptarshi BEJ

Dates

Publication Date : January 15, 2018

Bibtex @research article { jacodesmath349383, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2018}, volume = {5}, pages = {19 - 27}, doi = {10.13069/jacodesmath.349383}, title = {Coloring sums of extensions of certain graphs}, key = {cite}, author = {Kok, Johan and Bej, Saptarshi} }
APA Kok, J , Bej, S . (2018). Coloring sums of extensions of certain graphs . Journal of Algebra Combinatorics Discrete Structures and Applications , 5 (1) , 19-27 . DOI: 10.13069/jacodesmath.349383
MLA Kok, J , Bej, S . "Coloring sums of extensions of certain graphs" . Journal of Algebra Combinatorics Discrete Structures and Applications 5 (2018 ): 19-27 <https://dergipark.org.tr/en/pub/jacodesmath/issue/33304/349383>
Chicago Kok, J , Bej, S . "Coloring sums of extensions of certain graphs". Journal of Algebra Combinatorics Discrete Structures and Applications 5 (2018 ): 19-27
RIS TY - JOUR T1 - Coloring sums of extensions of certain graphs AU - Johan Kok , Saptarshi Bej Y1 - 2018 PY - 2018 N1 - doi: 10.13069/jacodesmath.349383 DO - 10.13069/jacodesmath.349383 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 19 EP - 27 VL - 5 IS - 1 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.349383 UR - https://doi.org/10.13069/jacodesmath.349383 Y2 - 2017 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Coloring sums of extensions of certain graphs %A Johan Kok , Saptarshi Bej %T Coloring sums of extensions of certain graphs %D 2018 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 5 %N 1 %R doi: 10.13069/jacodesmath.349383 %U 10.13069/jacodesmath.349383
ISNAD Kok, Johan , Bej, Saptarshi . "Coloring sums of extensions of certain graphs". Journal of Algebra Combinatorics Discrete Structures and Applications 5 / 1 (January 2018): 19-27 . https://doi.org/10.13069/jacodesmath.349383
AMA Kok J , Bej S . Coloring sums of extensions of certain graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2018; 5(1): 19-27.
Vancouver Kok J , Bej S . Coloring sums of extensions of certain graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2018; 5(1): 19-27.