Search

The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann. [ABSTRACT FROM AUTHOR]

The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n -uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with maximum edge degree at most Δ ( H ) ⩽ c ⋅ n r n − 1 is r -colorable, where c > 0 is an absolute constant. As an application of our proof technique we establish a new lower bound for Van der Waerden number W ( n , r ) , the minimum N such that in any r -coloring of the set { 1 , … , N } there exists a monochromatic arithmetic progression of length n . We show that W ( n , r ) > c ⋅ r n − 1 , for some absolute constant c > 0 . [ABSTRACT FROM AUTHOR]

Abstract: Consider a graph and, for each vertex , a subset of neighbors of . A -coloring is a coloring of the elements of so that vertices appearing together in some receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set , denoted by . In this paper we study graph classes for which there is a function , such that for any graph and any , there is a -coloring using at most colors. It is proved that if such a function exists for a class , then can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes. [Copyright &y& Elsevier]

Abstract: Let be a graph. A clique-transversal set is a subset of vertices of such that meets all cliques of , where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number, denoted by , of is the cardinality of a minimum clique-transversal set in . A -clique-coloring of is a -coloring of its vertices such that no clique is monochromatic. All planar graphs have been proved to be 3-clique-colorable by Mohar and Škrekovski [B. Mohar, R. Škrekovski, The Grötzsch theorem for the hypergraph of maximal cliques, Electron. J. Combin. 6 (1999) #R26]. Erdős et al. [P. Erdős, T. Gallai, Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math. 108 (1992) 279–289] proposed to find sharp estimates on for planar graphs. In this paper we first show that every outerplanar graph of order has and the bound is tight. Secondly, we prove that every claw-free planar graph different from an odd cycle is -clique-colorable and we present a polynomial-time algorithm to find the -clique-coloring. As a by-product of the result, we obtain a tight upper bound on the clique-transversal number for claw-free planar graphs. [Copyright &y& Elsevier]