Abstract. A graph [Formula: see text] is common if its Ramsey multiplicity, i.e., the minimum number of monochromatic copies of [Formula: see text] contained in any 2-edge-coloring of [Formula: see text], is asymptotically the same as the number of monochromatic copies in the random 2-edge-coloring of [Formula: see text]. Erdős conjectured that every complete graph is common, which was disproved by Thomason in the 1980s. Until today, a classification of common graphs remains a wide open and challenging problem. Grzesik et al. [ Combin. Probab. Comput., 31 (2022), 907–923] conjectured that every [Formula: see text]-apex of any connected Sidorenko graph is common. We prove for [Formula: see text] that the [Formula: see text]-apex of any tree is common.

Abstract. Erdős, Lovász, and Spencer showed in the late 1970s that the dimension of the region of [Formula: see text]-vertex graph profiles, i.e., the region of feasible densities of [Formula: see text]-vertex graphs in large graphs, is equal to the number of nontrivial connected graphs with at most [Formula: see text] vertices. We determine the dimension of the region of [Formula: see text]-vertex tournament profiles. Our result, which explores an interesting connection to Lyndon words, yields that the dimension is much larger than just the number of strongly connected tournaments, which would be the answer expected as the analogy to the setting of graphs.

Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. We prove that the twin-width of every graph embeddable in a surface of Euler genus $g$ is $18\sqrt{47g}+O(1)$, which is asymptotically best possible as it asymptotically differs from the lower bound by a constant multiplicative factor. Our proof also yields a quadratic time algorithm to find a corresponding contraction sequence. To prove the upper bound on twin-width of graphs embeddable in surfaces, we provide a stronger version of the Product Structure Theorem for graphs of Euler genus $g$ that asserts that every such graph is a subgraph of the strong product of a path and a graph with a tree-decomposition with all bags of size at most eight with a single exceptional bag of size $\max\{8,32g-27\}$.

Abstract. An oriented graph [Formula: see text] is quasirandom-forcing if the limit (homomorphism) density of [Formula: see text] in a sequence of tournaments is [Formula: see text] if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length [Formula: see text] is quasirandom-forcing if and only if [Formula: see text]. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to 10 are quasirandom-forcing.

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix $A$ and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of $A$, and when parameterized by the dual tree-depth and the entry complexity of $A$; both these parameterization imply that $A$ is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the $\ell_1$-norm of the Graver basis is bounded by a function of the maximum $\ell_1$-norm of a circuit of $A$. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix $A$ that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the $\ell_1$-norm of the Graver basis of the constraint matrix, when parameterized by the $\ell_1$-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with $n$ variables and a constraint matrix with dual tree-depth $d$ and largest entry $\Delta$ are solvable in time $g(d,\Delta){poly}(n)$ for some function $g$. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time $g(d^*,\Delta){poly}(n)$ where $d^*$ is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with tree-depth d and largest entry Δ are solvable in time g(d,Δ) poly(n) for some function g, i.e., fixed parameter tractable when parameterized by tree-depth d and Δ. However, the tree-depth of a constraint matrix depends on the positions of its non-zero entries and thus does not reflect its geometric structure. In particular, tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth. We prove that the branch-depth of the matroid defined by the columns of the constraint matrix is equal to the minimum tree-depth of a row-equivalent matrix. We also design a fixed parameter algorithm parameterized by an integer d and the entry complexity of an input matrix that either outputs a matrix with the smallest dual tree-depth that is row-equivalent to the input matrix or outputs that there is no matrix with dual tree-depth at most d that is row-equivalent to the input matrix. Finally, we use these results to obtain a fixed parameter algorithm for integer programming parameterized by the branch-depth of the input constraint matrix and the entry complexity. The parameterization by branch-depth cannot be replaced by the more permissive notion of branch-width.

We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G in G by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.

We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.

The Cyclic Coloring Conjecture asserts that the vertices of every plane graph with maximum face size $\Delta^*$ can be colored using at most $\lfloor3\Delta^*/2\rfloor$ colors in such a way that no face is incident with two vertices of the same color. The Cyclic Coloring Conjecture has been proven only for two values of $\Delta^*$: the case $\Delta^*=3$ is equivalent to the Four Color Theorem and the case $\Delta^*=4$ is equivalent to Borodin's Six Color Theorem, which says that every graph that can be drawn in the plane with each edge crossed by at most one other edge is 6-colorable. We prove the case $\Delta^*=6$ of the conjecture.

We show that for every hereditary permutation property and every ∊0 > 0, there exists an integer M such that if a permutation π is ∊o-far from in the Kendall's tau distance, then a random subpermutation of π of order M has the property P with probability at most ∊0. This settles an open problem whether hereditary permutation properties are strongly testable, i.e., testable with respect to the Kendall's tau distance, which is considered to be the edit distance for permutations. Our method also yields a proof of a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio on the relation of the rectangular distance and the Kendall's tau distance of a permutation from a hereditary property.

A seminal result of Reed et al. [15] in 1996 states that the Erdős-Pósa property holds for directed cycles, i.e. for every integer n there is an integer t such that every directed graph G has n pairwise vertex disjoint directed cycles or contains a set T ⊆ V (G) of at most t vertices such that G -T contains no directed cycle.In this paper, we consider the Erdős-Pósa property for directed cycles through a vertex in a given vertex set S, i.e. the question if for every integer n there is an integer t such that if G is a directed graph G and S is a set of vertices then G has n pairwise vertex disjoint directed cycles each containing a vertex of S or contains a set T of at most t vertices such that G-T contains no such directed cycle.For undirected graphs, this property holds for cycles through a vertex in a vertex set S (see Kakimura, Kawarabayashi and Marx [9], and Pontecorvi and Wollan [12]).In this paper, we show the following: The Erdős-Pósa does hold for half-integral packings of directed cycles each containing a vertex from S, i.e.where every vertex of the graph is contained in at most 2 cycles.On the other hand, an example shows that the Erdős-Pósa property does not hold without this relaxation.

We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nešetřil and Ossona de Mendez on the existence of low tree-depth colorings.

For every $d\ge 3$ and $k\in\{2\}\cup[3,\infty)$, we determine the smallest $\varepsilon$ such that every fractional $(k+\varepsilon)$-precoloring of vertices at mutual distance at least d of a graph G with fractional chromatic number equal to k can be extended to a proper fractional $(k+\varepsilon)$-coloring of G. Our work complements analogous results of Albertson for ordinary colorings and those of Albertson and West for circular colorings.

Let $\nu(G)$ be the maximum number of vertex-disjoint odd cycles of a graph $G$ and $\tau(G)$ the minimum number of vertices whose removal makes $G$ bipartite. We show that $\tau(G)\le 6\nu(G)$ if $G$ is planar. This improves the previous bound $\tau(G)\le 10\nu(G)$ by Fiorini et al. [Math. Program. Ser. B, 110 (2007), pp. 71--91].

An instance of a constraint satisfaction problem (CSP) is variable [Formula: see text]- consistent if any subinstance with at most [Formula: see text] variables has a solution. For a fixed constraint language [Formula: see text], [Formula: see text] is the largest ratio such that any variable [Formula: see text]-consistent instance has a solution that satisfies at least a fraction of [Formula: see text] of the constraints. We provide an expression for the limit [Formula: see text], and show that this limit coincides with the corresponding limit for constraint [Formula: see text]- consistent instances, i.e., instances where all subinstances with at most [Formula: see text] constraints have a solution. We also design an algorithm running in time polynomial in the size of input and [Formula: see text] that for an input instance and a given [Formula: see text] either computes a solution that satisfies at least a fraction of [Formula: see text] constraints or finds a set of inconsistent constraints whose size depends only on [Formula: see text]. Most of our results apply both to weighted and to unweighted instances of the CSP.

We show that every (sub)cubic [Formula: see text]-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978, which implies that it contains an independent set of size at least [Formula: see text]. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.

We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion. Many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no sub graph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We also develop an almost linear-time algorithm for deciding FOL properties in classes of graphs with locally bounded expansion, those include classes of graphs with locally bounded tree-width or locally excluding a minor. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FOL property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their addition results in a graph in the class. In addition, we design a dynamic data structure for testing existential properties or the existence of short paths between prescribed vertices in such classes of graphs. All our results also hold for relational structures and are based on the seminal result of Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.

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$.

Reed conjectured that for every $\varepsilon>0$ and every integer $\Delta$, there exists g such that the fractional total chromatic number of every graph with maximum degree $\Delta$ and girth at least g is at most $\Delta+1+\varepsilon$. The conjecture was proven to be true when $\Delta=3$ or $\Delta$ is even. We settle the conjecture by proving it for the remaining cases.

Gimbel and Thomassen asked whether 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for every surface which combined with previous results gives a linear-time algorithm to compute the chromatic number of such graphs. Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface Σ guarantees the existence of a subgraph H, whose size depends only on Σ, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the “winding number” of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends to find a 3-coloring. If the input triangle-free graph G drawn in Σ is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates Σ then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.

We show that the maximum number of colors that can be used in a vertex coloring of a cubic 3-connected plane graph G that avoids a face with vertices of mutually distinct colors (a rainbow face) is equal to $\frac{n}{2}+\mu^*-2$, where n is the number of vertices of G and $\mu^*$ is the size of the maximum matching of the dual graph $G^*$.

A notion of real number graph labellings captures the dependence of the span of an optimal channel assignment on the separations that are required between frequencies assigned to close transmitters. We determine the spans of such optimal labellings for a subfamily of Kneser graphs formed by the complements of the line graphs of complete graphs. This subfamily contains (among others) the Petersen graph.

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.

We prove that every n-vertex cubic bridgeless graph has at least $n/2$ perfect matchings and give a list of all 17 such graphs that have less than $n/2+2$ perfect matchings.

We show that every triangle-free graph on the double torus is 4-colorable. This settles a problem raised by Gimbel and Thomassen [Trans. Amer. Math. Soc., 349 (1997), pp. 4555–4564].

We establish new lower and upper bounds for the real number graph labelling problem. As an application, we consider a problem of Griggs to determine the optimum spans of $L(p,q)$-labellings of the infinite triangular plane lattice and find (using a computer) the optimum spans for all p and q.

Motivated by $L(p,q)$-labelings of graphs, we introduce a notion of $\lambda$-graphs: a $\lambda$-graph G is a graph with two types of edges: 1-edges and x-edges. For a parameter $x\in[0,1]$, a proper labeling of G is a labeling of vertices of G by nonnegative reals such that the labels of the endvertices of a 1-edge differ by at least 1 and the labels of the endvertices of an x-edge differ by at least x; $\lambda_G(x)$ is the smallest real such that G has a proper labeling by labels from the interval $[0,\lambda_G(x)]$. We study properties of the function $\lambda_G(x)$ for finite and infinite $\lambda$-graphs and establish the following results: if the function $\lambda_G(x)$ is well defined, then it is a piecewise linear function of x with finitely many linear parts. Surprisingly, the set $\Lambda(\alpha,\beta)$ of all functions $\lambda_G$ with $\lambda_G(0)=\alpha$ and $\lambda_G(1)=\beta$ is finite for any $\alpha\le\beta$. We also prove a tight upper bound on the number of segments for finite $\lambda$-graphs G with convex functions $\lambda_G(x)$.

A λ‐graph G is a (finite or infinite) graph with k types of edges, $x_1$‐edges,…, $x_k$‐edges. A labeling c of the vertices of G by nonnegative reals is proper with respect to reals $x_1,\ldots,x_k$ if the labels of the end‐vertices of an $x_i$‐edge differ by at least $x_i$. The span of the labeling c is the supremum of the labels used by c. The λ‐function $\lambda_G(x_1,\ldots,x_k)$ is the infimum of the spans of all the proper labelings with respect to $x_1,\ldots,x_k$. We show that the λ‐function of any graph G is piecewise linear in $x_1,\ldots,x_k$ with finitely many linear parts (unless the λ‐function is infinite). Moreover, we show that for all integers k and χ, there exist constants $C_{k,\chi}$ and $D_{k,\chi}$ such that the λ‐function of every λ‐graph G with k types of edges and chromatic number at most χ is comprised of at most $C_{k,\chi}$ linear parts, and that the coefficients of $x_1,\ldots,x_k$ of the linear functions comprising $\lambda_G(x_1,\ldots,x_k)$ are integers between 0 and $D_{k,\chi}$. Among others, our results yield proofs of the piecewise linearity conjecture, coefficient bound conjecture, and delta bound conjecture of Griggs and Jin [SIAM J. Discrete Math., 20 (2006), pp. 302–327].

An L(2,1)-labeling of a graph G is a mapping c : V(G) \to {0,...,K} such that the labels of two adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least one. A hole of c is an integer h \in {0,...,K} that is not used as a label for any vertex of G. The smallest integer K for which an L(2,1)-labeling of G exists is denoted by lambda(G). The minimum number of holes in an optimal labeling, i.e., a labeling with K = lambda(G), is denoted by rho(G). Georges and Mauro [SIAM J. Discrete Math., 19 (2005), pp. 208-223] showed that rho(G) \le Delta, where Delta is the maximum degree of G, and conjectured that if rho(G) = Delta and G is connected, then the order of G is at most Delta(Delta + 1). We disprove this conjecture by constructing graphs G with rho(G) = Delta and order \lfloor (Delta + 1) 2 /4 \rfloor (Delta + 1) \approx Delta 3 /4.

We study the notion of a generalized list T-coloring which is a common generalization of the channel assignment problem and the T-coloring. An instance of the generalized list T-coloring is described by a triple $(G,\Lambda,t)$, where G is a graph, $\Lambda$ is a mapping which assigns the vertices of G lists of numbers (colors), and t is a mapping which assigns each edge of G a set of forbidden differences. We require that $0\in t(e)$ for each edge e of G. The goal is to find a labeling c of the vertices of G with $c(v)\in\Lambda(v)$ for each vertex v, and $|c(u)-c(v)|\not\in t(uv)$ for each edge $uv$ of G. An instance is balanced if the size of the list $\Lambda(v)$ for each vertex v is equal to the sum of the sizes of $t(e)$ for edges e incident with v. We state and prove a Brooks-type theorem for the generalized list T-coloring problem. This generalizes and unifies the previously known Brooks-type theorems for the channel assignment problem and for the T-coloring. The theorem characterizes balanced instances of the generalized list T-coloring with a good labeling. As a consequence, if G is a connected graph different from a Gallai tree, then all balanced instances on G have good labelings.

We prove that the kth power G k of a chordal graph G with maximum degree $\Delta$ is $O(\sqrt{k}\Delta^{(k+1)/2})$-degenerate for even values of k and $O(\Delta^{(k+1)/2})$-degenerate for odd values. In particular, this bounds the chromatic number $\chi(G^k)$ of the kth power of G. The bound proven for odd values of k is the best possible. Another consequence is the bound $\lambda_{p,q}(G)\le\lfloor\frac{(\Delta+1)^{3/2}}{\sqrt{6}}\rfloor (2q-1)+\Delta(2p-1)$ on the least possible span $\lambda_{p,q}(G)$ of an L(p,q)-labeling for chordal graphs G with maximum degree $\Delta$. On the other hand, a construction of such graphs with $\lambda_{p,q}(G)\ge\Omega(\Delta^{3/2}q+\Delta p)$ is found.

A list channel assignment problem is a triple (G,L,w), where G is a graph, L is a function which assigns to each vertex of G a list of integers (colors), and w is a function which assigns to each edge of G a positive integer (its weight). A coloring c of the vertices of G is proper if c(v)\in L(v)$ for each vertex v and $|c(u)-c(v)|\ge w(uv)$ for each edge uv. A weighted degree $\deg_w(v)$ of a vertex v is the sum of the weights of the edges incident with v. If G is connected, $|L(v)|>\deg_w(v)$ for at least one v, and $|L(v)|\ge\deg_w(v)$ for all v, then a proper coloring always exists. A list channel assignment problem is balanced if $|L(v)|=\deg_w(v)$ for all v. We characterize all balanced list channel assignment problems (G,L,w) which admit a proper coloring. An application of this result is that each graph with maximum degree $\Delta\ge 2$ has an L(2,1)-labeling using integers $0,\ldots,\Delta^2+\Delta-1$.