Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Hoppen, Carlos [1] ; Lefmann, Hanno [2]
Total Authors: 2
Affiliation:
[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
Total Affiliations: 2
Document type: Journal article
Source: EUROPEAN JOURNAL OF COMBINATORICS; v. 47, p. 75-94, JUL 2015.
Web of Science Citations: 5
Abstract

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)

FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
Grantee:Carlos Eduardo Ferreira
Support Opportunities: Research Projects - Thematic Grants