Nonrepetitive edge-colorings of trees

MaRDI QIDQ4558962zbMATHFDO

Authors André Kündgen, Tonya Talbot

Publication date 30 November 2018

Full work available at URL https://arxiv.org/abs/1701.04227

zbMATH Keywords

square-free coloringThue coloringrepetition-free coloring

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Combinatorics on words (68R15)

Abstract: A repetition is a sequence of symbols in which the first half is the same as the second half. An edge-coloring of a graph is repetition-free or nonrepetitive if there is no path with a color pattern that is a repetition. The minimum number of colors so that a graph has a nonrepetitive edge-coloring is called its Thue edge-chromatic number. We improve on the best known general upper bound of $4Delta-4$ for the Thue edge-chromatic number of trees of maximum degree $Delta$ due to Alon, Grytczuk, Ha{l}uszczak and Riordan (2002) by providing a simple nonrepetitive edge-coloring with $3Delta-2$ colors.

Recommendations

• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of trees
• Nonrepetitive choice number of trees
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colorings of graphs -- a survey

Cited in

(9)

• Edge-Coloring Partialk-Trees
• scientific article; zbMATH DE number 1929924 (Why is no real title available?)
• A note about online nonrepetitive coloring \(k\)-trees
• Some results in square-free and strong square-free edge-colorings of graphs
• Repeated patterns in proper colorings
• On the long-repetition-free 2-colorability of trees
• Nonrepetitive colorings of trees
• Thue choosability of trees
• Nonrepetitive colorings of graphs

This page was built for publication: Nonrepetitive edge-colorings of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558962)