Nonrepetitive colorings of trees

A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by π(G). A famous theorem of Thue asserts that π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1 colors without repetitions on paths.     

Nonrepetitive colorings of graphs

A coloring of the vertices of a graph G is nonrepetitive if there is no even path in G whose first half looks the same as the second half. This notion arose as an analogue of the famous nonrepetitive sequences of Thue. We consider here the list analogue and the game analogue of nonrepetitive colorings.     

Nonrepetitive vertex colorings of graphs

We prove new upper bounds on the Thue chromatic number of an arbitrary graph and on the facial Thue chromatic number of a plane graph in terms of its maximum degree.     

Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor

We prove that graphs excluding a fixed immersion have bounded nonrepetitive chromatic number. More generally, we prove that if is a fixed planar graph that has a planar embedding with all the vertices with degree at least 4 on a single face, then graphs excluding as a topological minor have bounded nonrepetitive chromatic number. This is the largest class of graphs known to have bounded nonrepetitive chromatic number.     

Polychromatic colorings of bounded degree plane graphs

A polychromatic k‐coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G, one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K₄ or a subdivision of K₄ on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009     

Cyclic colorings of plane graphs with independent faces

Let G be a plane graph with maximum face size Δ^∗. If all faces of G with size four or more are vertex disjoint, then G has a cyclic coloring with Δ^∗+1 colors, i.e., a coloring such that all vertices incident with the same face receive distinct colors.     

Convex decompositions in the plane and continuous pair colorings of the irrationals

We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ² which is not presentable as a countable union of convex sets satisfies the following dichotomy:

Facially-constrained colorings of plane graphs: A survey

In this survey the following types of colorings of plane graphs are discussed, both in their vertex and edge versions: facially proper coloring, rainbow coloring, antirainbow coloring, loose coloring, polychromatic coloring, $?$-facial coloring, nonrepetitive coloring, odd coloring, unique-maximum coloring, WORM coloring, ranking coloring and packing coloring.In the last section of this paper we show that using the language of words these different types of colorings can be formulated in a more general unified setting.     

Facial unique-maximum colorings of plane graphs with restriction on big vertices

A facial unique-maximum coloring of a plane graph is a proper coloring of the vertices using positive integers such that each face has a unique vertex that receives the maximum color in that face. Fabrici and Göring (2016) proposed a strengthening of the Four Color Theorem conjecturing that all plane graphs have a facial unique-maximum coloring using four colors. This conjecture has been disproven for general plane graphs and it was shown that five colors suffice. In this paper we show that plane graphs, where vertices of degree at least four induce a star forest, are facially unique-maximum 4-colorable. This improves a previous result for subcubic plane graphs by Andova et al. (2018). We conclude the paper by proposing some problems.     

Annihilators in Nonrepetitive Semigroups

It is well known that one can construct an infinite sequence on three or more symbols such that no two consecutive blocks are identical. In this paper we give a combinatorial characterization for those finite sequences which are maximal in the sense that appending to them even one more symbol yields two consecutive identical blocks.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Facial Nonrepetitive Vertex Coloring of Plane Graphs

A sequence is a repetition. A sequence S is nonrepetitive, if no subsequence of consecutive terms of S is a repetition. Let G be a plane graph. That is, a planar graph with a fixed embedding in the plane. A facial path consists of consecutive vertices on the boundary of a face. A facial nonrepetitive vertex coloring of a plane graph G is a vertex coloring such that the colors assigned to the vertices of any facial path form a nonrepetitive sequence. Let denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol’ conjectured that can be bounded from above by a constant. We prove that for any plane graph G.     

Regular and canonical colorings

A general framework for coloring problems is described; the concept of regular coloring is introduced; it simply means that one specifies in each edge the maximum and the minimum number of nodes which may have the same color.For several types of regular colorings, one defines canonical colorings where colors form an ordered set and where one always tries to use first the “smallest” colors. It is shown that for some classes of multigraphs including bipartite multigraphs, regular edge colorings corresponding to maximal color feasible sequences are canonical.     

Eigenvalues and colorings of digraphs

Wilf’s eigenvalue upper bound on the chromatic number is extended to the setting of digraphs. The proof uses a generalization of Brooks’ Theorem to digraph colorings.     

Conditional colorings of graphs

For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χ_r(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated.     

The nonexistence of colorings

The purpose of this note is to prove the following result about the nonexistence of colorings.