Some bounds on local connective Chromatic number

Abstract

Graph coloring is one of the most important concept in graph theory. Many practical problems can be formulated as graph coloring problems. In this paper, we define a new coloring concept called local connective coloring. A local connective k-coloring of  a graph G is a proper vertex coloring, which assigns colors from   {1,2,...,k} to the vertices V(G) in a such way that any two non–adjacent vertices u and v of a color i satisfies k(u, v) > i, where k(u, v) is the maximum number of internally disjoint paths between u  and v. Adjacent vertices are colored with different colors as in the proper coloring. The smallest integer k for which there exists a local  connective k- coloring of G is called the local connective chromatic number of G, and it is denoted by clc(G).We study this coloring on  several classes of graphs and give some general bounds. We also compare local connective chromatic number of a graph with chromatic  number and packing chromatic number of it.

Keywords

• Graph coloring,packing chromatic number,internally disjoint path

References

1. A. Dandashi and M.Al-Mouhamed, Graph coloring for class scheduling, In Proceedings of IEEE/ACS International Conference on Computer Systems and Applications (AICCSA), 1–4, 2010.
2. A. Vasilyev, R. Darda and D. Stevanovi, Trees of Given Order and Independence Number with Minimal First Zagreb Index, MATCH Communications in Mathematical and in Computer Chemistry, 72, 775–782, 2014.
3. A. William and S. Roy, Packing Chromatic Number of Cycle Related Graphs, International Journal of Mathematics and Soft Computing, 4, 27–33, 2014.
4. B. Breˇsar, S. Klavˇzar, and D.F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math. 155, 2303–2311, 2007.
5. C.N. Lai, Optimal construction of all shortest node-disjoint paths in hypercubes with applications, IEEE Transactions on parallel and Distributed Systems, 23, 1129–1134, 2012.
6. F. Iqbal and F. A. Kuipers, Disjoint Paths in Networks,Wiley Encyclopedia of Electrical and Electronics Engineering,Wiley, 2015.
7. G. Chartrand, L. Lesniak, and P. Zhang. Graphs & Digraphs, Fifth edition, Taylor & Francis, 2010.
8. K. Menger, Zur allgemeinen Kurventheorie, Fundementa Mathematicae, 10, 96–115, 1927.

9. J.Topp and L.Volkmann, Sufficient conditions for equality of connectivity and minimum degree of a graph, Journal of Graph Theory 17, 695–700, 1993.
10. M. Klesc and S. Schrotter, On the packing chromatic number of semiregular polyhedra, Acta Electrotechnica et Informatica, 12, 27–31, 2012.
11. P.M.Talav´an and J.Y´a˜nez, The graph coloring problem: A neuronal network approach, European Journal of Operational Research, 191(1), 100–111, 2008.
12. R. Qu, E.K. Burke and B. McCollum, Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems, European Journal of Operational Research, 198(2), 392–404, 2009.
13. T. Park and C.Y. Lee, Application of the graph coloring algorithm to the frequency assignment problem, Journal of the Operations Research society of Japan, 39(2), 258–265, 1996.
14. W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris and D. F. Rall, Broadcast chromatic numbers of graphs, Ars Combinatoria, 86,33–50, 2008.