On square-free edge colorings of graphs

Janos Barat, P.P. Varju

    Research output: Contribution to journalJournal articleResearchpeer-review


    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.
    Original languageEnglish
    JournalArs Combinatoria
    Pages (from-to)377-383
    Publication statusPublished - 2008


    Dive into the research topics of 'On square-free edge colorings of graphs'. Together they form a unique fingerprint.

    Cite this