The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.

We prove that 1−o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n → ∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.

Abstract. Denote by [Formula: see text] the smallest eigenvalue of the signless Laplacian matrix of an [Formula: see text]-vertex graph [Formula: see text]. Brandt conjectured in 1997 that for regular triangle-free graphs [Formula: see text]. We prove a stronger result: If [Formula: see text] is a triangle-free graph, then [Formula: see text]. Brandt’s conjecture is a subproblem of two famous conjectures of Erdős: (1) Sparse-half-conjecture: Every [Formula: see text]-vertex triangle-free graph has a subset of vertices of size [Formula: see text] spanning at most [Formula: see text] edges. (2) Every [Formula: see text]-vertex triangle-free graph can be made bipartite by removing at most [Formula: see text] edges. In our proof we use linear algebraic methods to upper bound [Formula: see text] by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.

The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken over all non-null subgraphs $H \subseteq G$. For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.

Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values $R(K_4^-,K_4^-,K_4^-)=28$, $R(K_8,C_5)= 29$, $R(K_9,C_6)= 41$, $R(Q_3,Q_3)=13$, $R(K_{3,5},K_{1,6})=17$, $R(C_3, C_5, C_5)= 17$, and $R(K_4^-,K_5^-;3)= 12$. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.

Borrowing László Székely's lively expression, we show that Hill's conjecture is “asymptotically at least $98.5\%$ true.” This long-standing conjecture states that the crossing number cr$(K_n)$ of the complete graph $K_n$ is $H(n) := \frac{1}{4}{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{n-1}{2}\rfloor}{\lfloor\frac{n-2}{2}\rfloor}{\lfloor\frac{n-3}{2}\rfloor}$ for all $n\ge 3$. This has been verified only for $n\le 12$. Using the flag algebra framework, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large $n$, cr$(K_n) > 0.905\, H(n)$. Also using this framework, we prove that asymptotically cr$(K_n)$ is at least $0.985\, H(n)$. We also show that the spherical geodesic crossing number of $K_n$ is asymptotically at least $0.996\, H(n)$.

Dvořák, Král', and Thomas [ Three-Coloring Triangle-Free Graphs on Surfaces IV. Bounding Face Sizes of 4-Critical Graphs, preprint, arXiv:1404.6356v3, 2015; Three-Coloring Triangle-Free Graphs on Surfaces VI. 3-Colorability of Quadrangulations, preprint, arXiv:1509.01013, 2015] gave a description of the structure of triangle-free graphs on surfaces with respect to 3-coloring. Their description, however, contains two substructures (both related to graphs embedded in a plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.

Aksenov proved that in a planar graph $G$ with at most one triangle, every precoloring of a 4-cycle can be extended to a 3-coloring of $G$. We give an exact characterization of planar graphs with two triangles in which some precoloring of a 4-cycle does not extend. We apply this characterization to solve the precoloring extension problem from two 4-cycles in a triangle-free planar graph in the case that the precolored 4-cycles are separated by many disjoint 4-cycles. The latter result is used in follow-up papers [ SIAM J. Discrete Math., 31 (2017), pp. 865--874; SIAM J. Discrete Math., 32 (2018), pp. 94--105] to give detailed information about the structure of 4-critical triangle-free graphs embedded in a fixed surface.

By Brook's Theorem, every n-vertex graph of maximum degree at most Delta >= 3 and clique number at most Delta is Delta-colorable, and thus it has an independent set of size at least n/Delta. We give an approximate characterization of graphs with independence number close to this bound, and use it to show that the problem of deciding whether such a graph has an independent set of size at least n/Delta+k has a kernel of size O(k).

We study 3-coloring properties of triangle-free planar graphs $G$ with two precolored 4-cycles $C_1$ and $C_2$ that are far apart. We prove that either every precoloring of $C_1\cup C_2$ extends to a 3-coloring of $G$, or $G$ contains one of two special substructures which uniquely determine which 3-colorings of $C_1\cup C_2$ extend. As a corollary, we prove that there exists a constant $D>0$ such that if $H$ is a planar triangle-free graph and if $S\subseteq V(H)$ consists of vertices at pairwise distances at least $D$, then every precoloring of $S$ extends to a 3-coloring of $H$. This gives a positive answer to a conjecture of Dvořák, Král', and Thomas, and implies an exponential lower bound on the number of 3-colorings of triangle-free planar graphs of bounded maximum degree.

We show that if $G$ is a 4-critical graph embedded in a fixed surface $\Sigma$ so that every contractible cycle has length at least 5, then $G$ can be expressed as $G=G'\cup G_1\cup G_2\cup\cdots\cup G_k$, where $|V(G')|$ and $k$ are bounded by a constant (depending linearly on the genus of $\Sigma$) and $G_1, \ldots, G_k$ are graphs (of unbounded size) whose structure we describe exactly. The proof is computer assisted---we use a computer to enumerate all plane 4-critical graphs of girth 5 with a precolored cycle of length at most 16 that are used in the basic case of the inductive proof of the statement.

Consider the set of points formed by the integer $n\times n$ grid and the process that in each iteration removes from the point set the vertices of its convex hull. Here, we prove that the number of iterations of this process is $O\!\left(n^{4/3}\right)$; that is, the number of convex layers of the $n\times n$ grid is $\Theta\!\left(n^{4/3}\right)$.

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s i ,t i ) for i=1,…,k and is to test whether G contain k mutually induced paths P i such that P i connects s i and t i for i=1,…,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.

A graph G is k-choosable if G can be properly colored whenever every vertex has a list of at least k available colors. Thomassen's theorem states that every planar graph is 5-choosable. We extend the result by showing that every graph with at most two crossings is 5-choosable.

We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309 (2009), pp. 2948–2951] asking whether every graph with crossing number at most 5 and clique number at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be made planar by removing a few edges. In particular, we show that, if a graph with clique number at most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.

A graph is k-choosable if it can be colored whenever every vertex has a list of at least k available colors. We prove that if a triangle-free planar graph is not 3-choosable, then it contains a 4-cycle that intersects another 4- or 5-cycle in exactly one edge. This strengthens Thomassen's result [C. Thomassen, J. Combin. Theory Ser. B, 64 (1995), pp. 101–107] that every planar graph of girth at least 5 is 3-choosable. In addition, this implies that every triangle-free planar graph without 6- and 7-cycles is 3-choosable.

The shortest cycle cover conjecture of Alon and Tarsi asserts that the edges of every bridgeless graph with m edges can be covered by cycles of total length at most $7m/5=1.400m$. We show that every cubic bridgeless graph has a cycle cover of total length at most $34m/21\approx1.619m$, and every bridgeless graph with minimum degree three has a cycle cover of total length at most $44m/27\approx1.630m$.

We provide a complete list of 6-critical graphs that can be embedded on the Klein bottle settling a problem of Thomassen [J. Combin. Theory Ser. B, 70 (1997), pp. 67–100, Problem 3]. The list consists of nine nonisomorphic graphs which have altogether 18 nonisomorphic 2-cell embeddings and one embedding that is not 2-cell.