Coloring sums of extensions of certain graphs
Keywords:
Chromatic number, χ'-chromatic sum, χ -chromatic sum, Extended path, Extended cycleAbstract
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.
Downloads
References
A. Banerjee and S. Bej, On extension of regular graphs, arXiv:1509.05476 [math.CO] (2015).
J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, London, 2008.
S. Cabello and M. Jakovac, On the $b$–chromatic number of regular graphs, Discrete Appl. Math. 159(13) (2011) 1303–1310.
G. Chartrand and L. Lesniak, Graphs & Digraphs, 3rd ed., Chapman & Hall/CRC, Boca Raton, FL, 2000.
J. L. Gross and J. Yellen, Graph Theory and Its Applications, 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2006.
J. E. Hopcroft and R. M. Karp, An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2(4) (1973) 225–231.
J. Kok, N. K. Sudev, and K. P. Chithra, Generalised colouring sums of graphs, Cogent Math. 3(1) (2016) 1140002.
M. Kouider and A. El Sahili, About $b$–coloring of regular graphs, Research Report No. 1432, LRI, Université Paris-Sud, 2006.
E. Kubicka and A. J. Schwenk, An introduction to chromatic sums, In: Proc. 17th Annual ACM Computer Science Conference (CSC '89), ACM, New York (1989) 39–45.
P. C. Lisna and M. S. Sunitha, $b$–chromatic sum of a graph, Discrete Math. Algorithms Appl. 7(4) (2015) 1550047.
N. K. Sudev, K. P. Chithra, and J. Kok, Certain chromatic sums of some cycle-related graph classes, Discrete Math. Algorithms Appl. 8(3) (2016) 1650033.
