Some results in square-free and strong square-free edge-colorings of graphs |
| |
Authors: | KS Sudeep Sundar Vishwanathan |
| |
Institution: | Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, India |
| |
Abstract: | The set of problems we consider here are generalizations of square-free sequences A. Thue, Über unendliche Zeichenreichen, Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22]. A finite sequence a1a2…an of symbols from a set S is called square-free if it does not contain a sequence of the form ww=x1x2…xmx1x2…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 et al. N. Alon, J. Grytczuk, M. Ha?uszczak, O. Riordan, Nonrepetitive colorings of graphs, Random Struct. Algor. 21 (2002) 336-346] who proved bounds on the minimum number of colors needed for a square-free edge-coloring of G on the class of graphs with bounded maximum degree and trees. We discuss several variations of this problem and give a few new bounds. |
| |
Keywords: | Edge colorings Square-free colorings |
本文献已被 ScienceDirect 等数据库收录! |
|