The Strong Edge Coloring And Square-free Edge Coloring Of Some Special Graphs

In many projects like large super-network research, database systems research, timing research, circuit design research and so on, the theory of edge coloring can represent relationships between elements there. Due to its good application background, strong edge coloring theory has become a rapidly developing subject in the field of graph theory and also become one of the hot studies.As the concept of square-free coloring was introduced in graph theory by Alon in 2002. Square-free coloring has been rapid development as a new way of coloring in the last decade. Square-free coloring, square-free vertex coloring, square-free edge coloring have a wide range of application in many fields.A strong edge-coloring of a graph G is a proper edge-coloring, with the further condition that no two edges with the same color lay on a path of length three. The strong chromatic index is the minimum number of colors that allow a strong edge-coloring. A finite sequence a1 a2 an of symbols from a set S is called square-free if it does not contain a sequence of the form ww = x1 x2 xm x1 x2 xm, xi∈S as a subsequence of consecutive terms. Extending the above concept to graphs, a coloring of the edge set E in a graph G (V , E )is called square-free if the sequence of colors on any path in G is square-free. This was introduced by Alon in 2002.Firstly, we summarize the current research on coloring of general graph and related basic concepts. The study of these methods can be used indirectly to special graphs. In this paper, we consider some product graphs, and give their strong chromatic index.Then we introduce the concept of square-free coloring and the status of studying it. We discuss some properties of complete k-ary tree and d-dimensional hypercube and give a few new bounds. We remedy the error of the proposition 5 in [33] and then give a counterexample.