THERMAL SCIENCE

International Scientific Journal

Thermal Science - Online First

External Links

online first only

Packing chromatic number of transformation graphs

ABSTRACT
Graph coloring is an assignment of labels called colors to elements of a graph. The packing coloring was introduced by Goddard et. al. in 2008 which is a kind of coloring of a graph. This problem is NP-complete for general graphs. In this paper, we consider some transformation graphs and generalized their packing chromatic numbers.
KEYWORDS
PAPER SUBMITTED: 2019-07-20
PAPER REVISED: 2019-08-23
PAPER ACCEPTED: 2019-08-26
PUBLISHED ONLINE: 2019-10-06
DOI REFERENCE: https://doi.org/10.2298/TSCI190720363D
REFERENCES
  1. Chartrand, G., Lesniak, L., Zhang, P, Graphs and Digraphs, Chapman and Hall/CRC., New York, USA, 2016
  2. Goddard,W., Hedetniemi, S.M., Hedetniemi, S.T., Harris, J.M., Rall, D.F., Broadcast Chromatic Numbers of Graphs, Ars Combinatoria, 86 (2008), pp.33-49
  3. Fiala, J., Golovach P.A., Complexity of the Packing Coloring Problem for Trees, Discrete Applied Mathematics, 158 (2008), pp. 771-778
  4. Dunbar, J., Erwin, D., Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T. Broadcast in Graphs, Discrete Applied Mathematics, 154 (2006), pp. 59-75
  5. Bresar, B., Klavlar, S., Rall, D.F., On the Packing Chromatic Number of Cartesian Products, Hexagonal Latice and Trees, Discrete Applied Mathematics, 155 (2007), pp. 2303-2311
  6. Baoyindureng, W., Jixiang M. Basic Properties of Total Transformation Graphs, Journal of Mathematical Study, 34 (2001)
  7. Ekstein, J., Holub, P., Lidicky, B. Packing Chromatic Number of Distance Graphs, Discrete Applied Mathematics, 160 (2012), pp. 512-524
  8. Skiena, S. Cycles, Stars and Whells. Implementing Discrete Mathematics: Combinatories and Graph Theory with Mathematica, MA: Addison-Wesley, Cambridge, UK, 1990
  9. William A., Roy S., Packing Chromatic Number of Certain Graphs, International Journal of Pure and Applied Mathematics, 87 (2013), 6, pp.731-739
  10. Bondy J.A., Murty U.S.R., Graph Theory with Applications, Elsevier Science Publishing Co., Inc., USA, 1982
  11. Buckley, F., Harary, F. Distance in Graphs. Ed: Allan M. Wylde, Addison-Wesley Pub. Co, Michigan, Amerika,1990
  12. Ahlswede, R., Covering, Coloring, and Packing Hypergraphs, In Combinatorial Methods and Models, Springer, Cham., (2018), pp. 3-55.
  13. Balci, M. A., Atmaca, S. P., & Akgüller, Ö. Hyperpath Centers. In Advanced Computational Methods for Knowledge Engineering, Springer, Cham., (2016), pp. 129-137
  14. Balci, M. A., A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets. Afyon Kocatepe University Journal of Sciences and Engineering, (2017)
  15. Balci, M. A., & Akgüller, Ö., Average Weakly Hyperedge Domination Number for a Hyperpath and Actor-Network Application, International Journal of Modeling and Optimization, (2014), 4(5), 346
  16. Han, J., Treglown, A., The Complexity of Perfect Matchings and Packings in Dense Hypergraphs, Journal of Combinatorial Theory, Series B, (2019)
  17. Kunszenti-Kovacs, D., Lovasz, L., & Szegedy, B. Measures on the Square as Sparse Graph Limits, Journal of Combinatorial Theory, Series B, (2019)
  18. Dehmer, M., Emmert-Streib, F., Chen, Z., Li, X., & Shi, Y. (Eds), Mathematical Foundations and Applications of Graph Entropy, Wiley-VCH, (2016)
  19. Akgüller, Ö., & Balcı, M. A., Geodetic Convex Boundary Curvatures of the Communities in Stock Market Networks, Physica A: Statistical Mechanics and its Applications, (2018), 505, 569-581