An edge coloring of the n-vertex complete graph Kn is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that the number of Gallai colorings of Kn with at most three colors is at most 7(n+1)2n2, which improves the best known upper bound of 32(n−1)!⋅2n−12 in Benevides et al. (2017) .

An edge coloring of the n-vertex complete graph, K_n, is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that for n large and every k with k≤2n/4300, the number of Gallai colorings of K_n that use at most k given colors is ((k^2)+o_n(1))2(n^2). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2n/2.

A (proper) k-coloring of a graph G = (V,E) is a function c:V(G)→1,\ldots,k such that c(u)≠c(v) for every uv∈E(G). Given a graph G and a spanning subgraph H of G, a circular q-backbone k-coloring of (G,H) is a k-coloring c of G such that q≤|c(u)−c(v)|≤k−q for every edge uv∈E(H). The circular q-backbone chromatic number of (G,H), denoted by CBCq(G,H), is the minimum integer k for which there exists a circular q-backbonek-coloring of (G,H). The Four Color Theorem implies that if G is planar, we have CBC2(G,H)≤8. It is conjectured that this upper bound can be improved to 7 when H is a tree, and to 6 when H is a matching. In this work, we present some partial results towards these bounds. We first prove that if G is planar containing no C4 as subgraph and H is a linear spanning forest of G, then CBC2(G,H)≤7. Then, we show that if G is a plane graph having no two 3-faces sharing an edge and H is a matching of G, then CBC2(G,H)≤6. Finally, we decrease the bound and show that if G is a planar graph having no C4 nor C5 as subgraph and H is a matching of G, then CBC2(G,H)≤5. Our results partially answer some questions raised by the community. In particular, the proofs use the Discharging Method, and this fact answers questions about whether one could prove such bounds for planar graphs without using the Four Color Theorem.

We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set X of n elements we want to identify an unknown subset Y of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.

Given a graph F and an integer r≥2, a partition F̂ of the edge set of F into at most r classes, and a graph G, define c_r,F̂(G) as the number of r-colorings of the edges of G that do not contain a copy of F such that the edge partition induced by the coloring is isomorphic to the one of F. We think of F̂ as the pattern of coloring that should be avoided. The main question is, for a large enough n, to find the (extremal) graph G on n vertices which maximizes c_r,F̂(G). This problem generalizes a question of Erdős and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where F is a clique and the partition F̂ contains a single class). We use Hölder’s Inequality together with Zykov’s Symmetrization to prove that, for any r≥2, k≥3 and any pattern K̂_k of the clique K_k, there exists a complete multipartite graph that is extremal. Furthermore, if the pattern K̂_k has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that r = 3 and F̂ is a rainbow triangle (that is, where F = K_3 and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for r = 3, we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.

The vertices of the kth power of a directed path with n vertices are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already appeared. The selector’s aim is to choose on-line the maximal vertex (i.e., the vertex with no outgoing edges). We give upper and lower bounds for the asymptotic behaviour of p_n,kn^1/(k+1), where pn,k is the probability of success under the optimal algorithm. In order to derive the upper bound, we consider a model in which the selector obtains some extra information about the edges that have already appeared. We give the exact asymptotics of the probability of success under the optimal algorithm in this case. In order to derive the lower bound, we analyse a site percolation process on a sequence of the kth powers of a directed path with n vertices.

Recent papers investigated the maximum infection time tP3(G) of the P3-convexity (also called maximum time of 2-neighbor bootstrap percolation) and the maximum infection time tmo(G) of the monophonic convexity. In 2014, it was proved that, for bipartite graphs, deciding whether tP3(G)≥k is polynomial time solvable for k≤4, but is NP-complete for k≥5 [23]. In 2015, it was proved that deciding whether tmo(G)≥2 is NP-complete even for bipartite graphs [12]. In this paper, we investigate the maximum infection time tgd(G) of the geodesic convexity. We prove that deciding whether tgd(G)≥k is polynomial time solvable for k = 1, but is NP-complete for k≥2 even for bipartite graphs. We also present an O(n3m)-time algorithm to determine tgd(G) and tmo(G) in distance-hereditary graphs. For this, we characterize all minimal hull sets of a general graph in the monophonic convexity. Moreover, we improve the complexity of the fastest known algorithm for finding a minimum hull set of a general graph in the monophonic convexity.

In the geodetic convexity of a graph G, we define the interval of a set S⊆V(G) as the set formed by S and all vertices in all shortest paths with endpoints in S. We say S is convex if it is equal to its interval. The convex hull of S can be obtained by repeatedly applying the interval function until obtaining a convex set. Here we consider the problem of determining the maximum k such that there is a set of vertices S, whose convex hull is V (G), such that it is necessary at least k applications of the interval function to obtain V (G). We show that this problem is NP-complete for bipartite graphs and give a polynomial time algorithm for distance-hereditary graphs.

In 2-neighbourhood bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. In this paper, we are interested to calculate the maximal time t(G) the process can take, in terms of the number of times the interval function is applied, to eventually infect the entire vertex set. We prove that the problem of deciding if t(G)≥k is NP-complete for: (a) fixed k≥4; (b) bipartite graphs and fixed k≥7; and (c) planar graphs. Moreover, we obtain linear and polynomial time algorithms for trees and chordal graphs, respectively.

We consider a classic model known as bootstrap percolation on the n \times n square grid. To each vertex of the grid we assign an initial state, infected or healthy, and then in consecutive rounds we infect every healthy vertex that has at least two already infected neighbors. We say that percolation occurs if the whole grid is eventually infected. In this paper, contributing to a recent series of extremal results in this field, we prove that the maximum time a bootstrap percolation process can take to eventually infect the entire vertex set of the grid is 13n^2/18+O(n).

A connected vertex ordering of a graph G is an ordering v1 < v2 < ··· < vn of V(G) such that vi has at least one neighbour in v1,...,vi−1, for every i ∈ 2, . . . , n. A connected greedy colouring is a colouring obtained by the greedy algorithm applied to a connected vertex ordering. In this paper we study the parameter Γc(G), which is the maximum k such that G admits a connected greedy k-colouring, and χc(G), which is the minimum k such that a connected greedy k-colouring of G exists. We prove that computing Γc(G) is NP-hard for chordal graphs and complements of bipartite graphs. We also prove that if G is bipartite, Γc(G) = 2. Concerning χc(G), we first show that there is a k-chromatic graph Gk with χc(Gk) > χ(Gk), for every k ≥ 3. We then prove that for every graph G, χc(G) ≤ χ(G) + 1. Finally, we prove that deciding if χc(G) = χ(G), given a graph G, is a NP-hard problem.

Bootstrap percolation, one of the simplest cellular automata, can be seen as a model of the spread of infection. In r-neighbour bootstrap percolation on a graph G we assign a state, infected or healthy, to every vertex of G and then update these states in successive rounds, according to the following simple local update rule: infected vertices of G remain infected forever and a healthy vertex becomes infected if it has at least r already infected neighbours. We say that percolation occurs if eventually every vertex of G becomes infected. A well known and celebrated fact about the classical model of 2-neighbour bootstrap percolation on the n times n square grid is that the smallest size of an initially infected set which percolates in this process is n. In this paper we consider the problem of finding the maximum time a 2-neighbour bootstrap process on [n]^2 with n initially infected vertices can take to eventually infect the entire vertex set. Answering a question posed by Bollob ́as we compute the exact value for this maximum showing that, for n ≥ 4, it is equal to the integer nearest to (5n^2 − 2n)/8.

Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree δ(G) > 3n/4 contains a monochromatic cycle of length ℓ, for all ℓ ∈ [4, ⌈n/2⌉]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with δ(G)=3n/4 that do not contain all such cycles. Finally, we show that, for all δ>0 and n>n0(δ), if G is a 2-edge coloured graph of order n with δ(G) ≥ 3n/4, then one colour class either contains a monochromatic cycle of length at least (2/3+δ/2)n, or contains monochromatic cycles of all lengths ℓ ∈ [3, (2/3−δ)n].

In this article we study multipartite Ramsey numbers for odd cycles. Our main result is the proof that a conjecture of Gyárfás et al. (J Graph Theory 61 (2009), 12–21), holds for graphs with a large enough number of vertices. Precisely, there exists n0 such that if n≥n0 is a positive odd integer then any two-coloring of the edges of the complete five-partite graph K_(n−1)/2,(n−1)/2,(n−1)/2,(n−1)/2,1 contains a monochromatic cycle of length n

Denote by R(L, L, L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdős conjectured that when L is the cycle Cn on n vertices, R(Cn,Cn,Cn) = 4n − 3 for every odd n > 3. Łuczak proved that if n is odd, then R(Cn, Cn, Cn) = 4n + o(n), as n → ∞, and Kohayakawa, Simonovits and Skokan confirmed the Bondy-Erdős conjecture for all sufficiently large values of n. Figaj and Łuczak determined an asymptotic result for the ‘complementary’ case where the cycles are even: they showed that for even n, we have R(Cn,Cn,Cn) = 2n + o(n), as n → ∞. In this paper, we prove that there exists n1 such that for every even n ≥ n1, R(Cn,Cn,Cn) = 2n

Motivated by a question of Sárközy, we investigate sufficient conditions for existence of infinite sets of natural numbers A and B such that the number of solutions of the equation a + b = n where a ∈ A and b ∈ B is monotone increasing for n > n0. We also examine a generalized notion of Sidon sets. That is, sets A, B with the property that, for every n ≥ 0, the equation above has at most one solution, i.e., all pairwise sums are distinct.