Problema de Erdös-Rothschild em certos padrões de coloração de grafos conexos

Abstract

A pattern ˆF is a graph with a precoloring of its edges. If G is a graph, then an edge-coloring of G avoids ˆF if G does not contain a subgraph isomorphic to F (considering also a color-preserving isomorphism). In this dissertation, we mention some known results, such as: (i) If ˆF is the pattern of a complete graph, then for any positive integer n, one of the n-vertex graphs that maximizes the number of colorings avoiding ˆF is a complete multipartite graph. (ii) If ˆF is the pattern of a monochromatic complete graph with k+1 vertices and r = 2 or 3, then for any sufficiently large positive integer n, the graph that maximizes the number of r-colorings avoiding ˆF is the Turán graph with n vertices and k parts. (iii) If ˆF is a monochromatic star with t +1 vertices, then for any graph G with n vertices, the number of r-colorings of G that avoid ˆF is at most Ä (r(t − 1))!(t − 1)! r ä n2 . The contributions of this work are: (iv) If ˆF is the pattern of a complete graph with at least 700 vertices and at most 5 colors, then for all sufficiently large r, the n-vertex graph that maximizes the number of r-colorings avoiding ˆF is not the Turán graph with n vertices and k parts. (v) Letting ˆF be a monochromatic star with t +1 vertices, there exists a graph G with n vertices such that the number of r-colorings of G that avoid ˆF is at least f (r) n(t − 1)2 , where f (r) ∼2πr Ä re2 är.