Edge-colorings avoiding a fixed matching with a prescribed color pattern

Autor(es)

Hoppen, Carlos ^[1] ; Lefmann, Hanno ^[2]

Afiliação do(s) autor(es)

^[1] Univ Fed Rio Grande do Sul, Inst Matemat, BR-91509900 Porto Alegre, RS - Brazil

^[2] Tech Univ Chemnitz, Fak Informat, D-09107 Chemnitz - Germany

• Tipo de documento: Artigo Científico
• Fonte: EUROPEAN JOURNAL OF COMBINATORICS; v. 47, p. 75-94, JUL 2015.
• Citações Web of Science: 5

Resumo

We consider an extremal problem motivated by a question of Erdos and Rothschild (Erdos, 1974) regarding edge-colorings of graphs avoiding a given monochromatic subgraph. An extension of this problem to edge-colorings avoiding fixed subgraphs with a prescribed coloring has been studied by Balogh (Balogh, 2006). In this work, we consider the following natural generalization of the original Erdos-Rothschild question: given a natural number r and a graph F, an r-pattern P of F is a partition of the edge set of F into r (possibly empty) classes, and an r-coloring of the edge set of a graph G is said to be (F, P)-free if it does not contain a copy of F in which the partition of the edge set induced by the coloring has a copy of P. Let C-r,((F,P))(G) be the number of (F, P)-free r-colorings of a graph G. For large n, we maximize this number over all n-vertex graphs for a large class of patterns in matchings and we describe the graphs that achieve this maximum. (C) 2015 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático