An Investigation on Non-Repetitive Coloring of Trees

Overview

Thue and Alon has laid the foundation of non-repetitive vertex colorings for certain graphs, discovering and proving many of its theorems. In this paper we explore the problem of how many colors do we need to non-repetitively color trees. As trees contain multi-degree vertices while a path only has vertices with degree 1 or 2, we suspect that being the determining characteristic that makes a tree unable to be 3-colored. Therefore, we try to investigate how this structure alone affects the coloring. With this in mind, we initially limited the number of such multi-degree vertices to 1, or star-subdivisions. We hypothesize that star-subdivisions are often 3-colorable. To prove this conjecture, we initially found colorings that are 3-colorable then tried to “fit” them into a star-subdivision. We successfully found two special colorings which can 3-color any star-subdivision, proving that some special trees are indeed 3-colorable. Then, we pushed this investigation further to investigate when there are more than 1 multi-degree vertices, and it turns out there are indeed some cases where such graphs can be 3-colorable. This allowed us to become one step nearer to discover the specific amount of colors needed to color certain types of trees.

Competition history

• ISEF 2022 Mathematics · Entry MATH003 · Atlanta, Georgia, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.