Edge colorings avoiding patterns*

We say that a pattern is a graph together with an edge coloring, and a pattern P = (H, c) occurs in some edge coloring c ' of G if c ', restricted to some subgraph of G isomorphic to H, is equal to c up to renaming the colors. Inspired by Matousek's visibility blocking problem, we study edge colorings that avoid certain patterns. We show that for every pattern P, such that the number of edges in P is at least the number of vertices in P plus the number of colors minus 2, there is a constant C such that every graph with maximum degree increment admits an edge coloring with C increment colors avoiding P; the same also holds for infinite sets of such patterns, provided that the number of patterns in the set grows at most exponentially. (c) 2023 Elsevier Ltd. All rights reserved.