Journal article
On square-free edge colorings of graphs
An edge coloring of a graph is called square-free, if the sequence of colors on certain walks is not a square, that is not of the form x(1,)...,x(m), x(1),...,x(m), for any m epsilon N. Recently, various classes of walks have been suggested to be considered in the above definition. We construct graphs, for which the minimum number of colors needed for a square-free coloring is different if the considered set of walks vary, solving a problem posed by Bre ar and Klav2ar.
We also prove the following: if an edge coloring of G is not square-free (even in the most general sense), then the length of the shortest square walk is, at most 8 vertical bar E(G)vertical bar(2). Hence, the necessary number of colors for a square-free coloring is algorithmically computable.
Language: | English |
---|---|
Year: | 2008 |
Pages: | 377-383 |
ISSN: | 28175204 and 03817032 |
Types: | Journal article |