Nonrepetitive edge-colorings of trees

zbMATH Open1400.05055arXiv1701.04227MaRDI QIDQ4558962FDOQ4558962

Authors: André Kündgen, Tonya Talbot 

Publication date: 30 November 2018

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.

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

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

zbMATH Keywords

square-free coloringThue coloringrepetition-free coloring

Mathematics Subject Classification ID

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

Cited In (9)

• On the long-repetition-free 2-colorability of trees
• Title not available (Why is that?)
• Nonrepetitive colorings of graphs
• Repeated patterns in proper colorings
• Thue choosability of trees
• Edge-Coloring Partialk-Trees
• Some results in square-free and strong square-free edge-colorings of graphs
• Nonrepetitive colorings of trees
• A note about online nonrepetitive coloring \(k\)-trees

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)