Record Details

Some results in square-free and strong square-free edge-colorings of graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Some results in square-free and strong square-free edge-colorings of graphs
 
Creator SUDEEP, KS
VISHWANATHAN, SUNDAR
 
Subject edge detection
graphs
theorem proving
color
 
Description 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,xiset membership, variantS, 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.
 
Publisher Elsevier
 
Date 2009-05-14T13:40:07Z
2011-12-08T07:17:35Z
2011-12-26T13:02:04Z
2011-12-27T05:48:00Z
2009-05-14T13:40:07Z
2011-12-08T07:17:35Z
2011-12-26T13:02:04Z
2011-12-27T05:48:00Z
2007
 
Type Article
 
Identifier Discrete Mathematics 307(14), 1818-1824
0012-365X
10.1016/j.disc.2006.09.019
http://hdl.handle.net/10054/1362
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1362
 
Language en