Coloring the Dth Power of The Cartesian Product of Two Cycles and Two Paths

Volume 16, Issue 1, pp 8-17 http://dx.doi.org/10.22436/jmcs.016.01.02

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 3465 Downloads
• 4335 Views

Authors

Elham Sharifi Yazdi - Department of Computer Engineering, Imam Javad University College, Yazd, Iran.

Abstract

The \(d^{th}\) power graph \(G^d\) is defined on the vertex set of a graph \(G\) in such a way that distinct vertices with distance at most \(d\) in \(G\) are joined by an edge. In this paper the chromatic number of the \(d^{th}\) power of the Cartesian product \(C_m\square C_n\) of two cycles is studied and some of the exact value of \(\chi((C_m\square C_n)^d)\) with conditions are determined. Also the chromatic number of the \(d^{th}\) power of grid \(P_m\square P_n\) with some conditions are determined and the exact value of \(\chi((P_m\square P_n)^d)\) for \(n = 2, 3\) is obtained.

Share and Cite

Keywords

• Chromatic number
• power graphs
• distance \(d\) coloring
• Cartesian product of cycles
• Cartesian product of paths.

MSC

•  05C12
•  05C15
•  05C76

References

• [1] S. H. Chiang, J. H. Jan, On L(d,1)-labeling of Cartesian product of a cycle and a path, Discrete Appl. Math., 156 (2008), 2867-2881.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [2] Z. Dvořák, D. Král, P. Nejedlý, R. Škrekovski , Coloring squares of planar graphs with girth six, J. Combin., 29 (2008), 838-849.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [3] R. E. Jamison, G. L. Matthews, Distance k colorings of Hamming graphs, In proceedings of the thirty seventh southeastern International Conference on combinatorics, Graph Theory and Computing, 183 (2006), 193-202.
  • MathSciNet
  • Google Scholar


• [4] F. Kramer, H. Kramer, A survey on the distance colouring of graphs, Discrete Math., 308 (2008), 422-426.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [5] K. W. Lih, W. Wan, Coloring the square of an outerplanar graph, Taiwanese J. Math., 10 (2006), 1015-1023.
  • View Article
  • MathSciNet
  • Google Scholar


• [6] M. Molloy, M. R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B,, 94 (2005), 189-213.
  • View Article
  • MathSciNet
  • Google Scholar


• [7] K. Selvakumar, S. Nithya, \(d_2\)-coloring of a graph, J. Math. Comput. Sci., 3 (2011), 102-111.


• [8] E. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math., 310 (2010), 2327-2333.
  • View Article
  • MathSciNet
  • Google Scholar