Dergiler / New Trends in Mathematical Sciences / 2017 / Cilt: 5 Sayı: 2

Some bounds on local connective Chromatic number

Sayfa
204–211
Yayın Tarihi
2017-03-30
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

We also compare local connective chromatic number of a graph with chromatic number and packing chromatic number of it.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:Graph coloring is one of the most important concept in graph theory.
📊
Temel Bulgular & Veri: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.
💡
Sonuç & Katkı:We also compare local connective chromatic number of a graph with chromatic number and packing chromatic number of it.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Graph coloring · packing chromatic number · internally disjoint path

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.

🔖

Bu Makaleye Atıf Yap

Ciftci, C., DUNDAR, P. (2017). Some bounds on local connective Chromatic number. New Trends in Mathematical Sciences, Cilt: 5 Sayı: 2, 204–211. https://ajindex.com/articles/1003744

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (12)

  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. 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.
  4. 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.
  5. F. Iqbal and F. A. Kuipers, Disjoint Paths in Networks,Wiley Encyclopedia of Electrical and Electronics Engineering,Wiley, 2015.
  6. G. Chartrand, L. Lesniak, and P. Zhang. Graphs & Digraphs, Fifth edition, Taylor & Francis, 2010.
  7. K. Menger, Zur allgemeinen Kurventheorie, Fundementa Mathematicae, 10, 96–115, 1927.
  8. 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.
  9. M. Klesc and S. Schrotter, On the packing chromatic number of semiregular polyhedra, Acta Electrotechnica et Informatica, 12, 27–31, 2012. 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.
  10. 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.
  11. 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.
  12. 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.