Coloring The Square Of Graphs

The square of a graph G, denoted by G2, is a graph with the same vertex set such that two vertices are adjacent in G2 iff their distance is at most 2 in G. For integers p, q 0, a labelling of a graph V(G) {0,1, ??? n}, for a certain n 0, is called an L(p, q)-labelling if it satisfies: whenever distG(u,v) = 1 and whenever distG(u,v) = 2. The (p, q)-span of a graph G, denoted by X(G;p,q), is the minimum n for which an L(p,q)-labelling exists. In this article we consider the chromatic number of the square of the following graph classes: cycles, trees, Halin graphs, outerplanar graphs and planar graphs without i-cycles, where 4 i 9, and get a range of the chromatic number of those graphs. For outerplanar graphs and planar graphs without i-cycles, where 4 i 9, we also extend the bound of the chromatic number of those graphs to L(p,q)-labelling of them. By the proof of the main results of this article, we give an O(n2) time algorithm for finding a coloring of G2 with A + 6 colors at most. At the end of this article we list some unsolved problems which is interested to consider in my future study.