We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size $t$ in a bipartite graph $G$ with a fixed bipartition is an independent set with exactly $t$ vertices in each part; in other words, it is a copy of $K_{t, t}$ in the bipartite complement of $G$. Let $f(n, \Delta)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $\Delta$ in one of the parts has a bi-hole of size $k$. Determining $f(n, \Delta)$ is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. It has connections to the bipartite version of the Erdös--Hajnal conjecture, bipartite Ramsey numbers, and the Zarankiewicz problem. Our main result determines the asymptotic behavior of $f(n, \Delta)$. More precisely, we show that for large but fixed $\Delta$ and $n$ sufficiently large, $f(n, \Delta) = \Theta(\frac{\log \Delta}{\Delta} n)$. We further address more specific regimes of $\Delta$, especially when $\Delta$ is a small fixed constant. In particular, we determine $f(n, 2)$ exactly and obtain bounds for $f(n, 3)$, though determining the precise value of $f(n, 3)$ is still open.

We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree $\Delta \ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of $\Delta$, and improves it when $\Delta\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of $\Delta$, we also demonstrate that every graph of girth at least $7$ and maximum degree $\Delta$ has fractional chromatic number at most $1+ \min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth $7$ and maximum degree $\Delta$ is at most $\frac{2\Delta+9}{5}$ when $\Delta \in [3,8]$, at most $\frac{\Delta+7}{3}$ when $\Delta \in [8,20]$, at most $\frac{2\Delta+23}{7}$ when $\Delta \in [20,48]$, and at most $\frac{\Delta}{4}+5$ when $\Delta \in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree $\Delta \in \{3,4,5\}$ and girth $g\in \{6,\dotsc,12\}$, notably $1/3$ when $(\Delta,g)=(4,10)$ and $2/7$ when $(\Delta,g)=(5,8)$.

The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.

Let $G$ be a graph of order $n$. Let $\mathrm{lpt}(G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $X$ intersects every longest path of $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead of paths. We prove that $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if $G$ is connected, and $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ if $G$ is $2$-connected. Our bound on $\mathrm{lct}(G)$ improves an earlier result of Thomassen. Furthermore, we prove upper bounds on $\mathrm{lpt}(G)$ for planar graphs and graphs of bounded tree-width.

We use distributed computing tools to provide a new perspective on the behavior of cooperative biological ensembles. We introduce the Ants Nearby Treasure Search (ANTS) problem, a generalization of the classical cow-path problem [10, 20, 41, 42], which is relevant for collective foraging in animal groups. In the ANTS problem, k identical (probabilistic) agents, initially placed at some central location, collectively search for a treasure in the two-dimensional plane. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both k and D, where D is the distance between the central location and the target. This is biologically motivated by cooperative, central place foraging, such as performed by ants around their nest. In this type of search there is a strong preference to locate nearby food sources before those that are further away. We focus on trying to find what can be achieved if communication is limited or altogether absent. Indeed, to avoid overlaps agents must be highly dispersed making communication difficult. Furthermore, if the agents do not commence the search in synchrony, then even initial communication is problematic. This holds, in particular, with respect to the question of whether the agents can communicate and conclude their total number, k. It turns out that the knowledge of k by the individual agents is crucial for performance. Indeed, it is a straightforward observation that the time required for finding the treasure is Ω(D + D2/k), and we show in this paper that this bound can be matched if the agents have knowledge of k up to some constant approximation.

An $L(p,1)$-labeling of a graph is a function f from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices x and y in the graph. The span of an $L(p,1)$-labeling f is the difference between the largest and the smallest labels used by f. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$. We settle this conjecture for $\Delta$ sufficiently large. More generally, we show that for any positive integer p there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$. This yields that for each positive integer p, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labeling with span at most $\Delta^2+C_p$.

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

Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (Δ+1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [33], as well as the OΔ2-coloring algorithm by Linial [27]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, they assume that all nodes know good estimations of one or more global parameters of the network, e.g., the maximum degree Δ or the number of nodes n.

An edge-face coloring of a plane graph with edge set [Formula: see text] and face set [Formula: see text] is a coloring of the elements of [Formula: see text] such that adjacent or incident elements receive different colors. Borodin [2 2 ] proved that every plane graph of maximum degree [Formula: see text] can be edge-face colored with [Formula: see text] colors. Borodin’s bound was recently extended to the case where [Formula: see text]. In this paper, we extend it to the case [Formula: see text].

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.

A proper vertex coloring of a graph G is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $\chi_{eq}^*(G)$ of G is the smallest integer m such that G is equitably n-colorable for all $n\geq m$. We show that for planar graphs G with minimum degree at least two, $\chi_{eq}^*(G)\leq4$ if the girth of G is at least 10, and $\chi_{eq}^*(G)\leq3$ if the girth of G is at least 14.

Abstract Motivated by a satellite communications problem, we consider a generalized coloring problem on unit disk graphs. A coloring is k‐improper if no more than k neighbors of every vertex have the same colour as that assigned to the vertex. The k‐improper chromatic number χk(G) is the least number of colors needed in a k‐improper coloring of a graph G. The main subject of this work is analyzing the complexity of computing χk for the class of unit disk graphs and some related classes, e.g., hexagonal graphs and interval graphs. We show NP‐completeness in many restricted cases and also provide both positive and negative approximability results. Because of the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing χk for unit interval graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

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.

In 1981, Bermond and Thomassen conjectured that every digraph with minimum out-degree at least $2k-1$ contains k disjoint cycles. This conjecture is trivial for $k=1$, and was established for $k=2$ by Thomassen in 1983. We verify it for the next case, proving that every digraph with minimum out-degree at least five contains three disjoint cycles. To show this, we improve Thomassen's result by proving that every digraph whose vertices have out-degree at least three, except at most two with out-degree two, indeed contains two disjoint cycles.

A plane graph is ł-facially k-colorable if its vertices can be colored with k colors such that any two distinct vertices on a facial segment of length at most łare colored differently. We prove that every plane graph is 3-facially $11$-colorable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically $11$-colorable. These two bounds are just one higher than those that are proposed by the $(3\l+1)$-conjecture and the cyclic conjecture.

The central problem of the total-colorings is the total-coloring conjecture, which asserts that every graph of maximum degree $\Delta$ admits a $(\Delta+2)$-total-coloring. Similar to edge-colorings—with Vizing's edge-coloring conjecture—this bound can be decreased by 1 for plane graphs of higher maximum degree. More precisely, it is known that if $\Delta\ge10$, then every plane graph of maximum degree $\Delta$ is $(\Delta+1)$-totally-colorable. On the other hand, such a statement does not hold if $\Delta\le3$. We prove that every plane graph of maximum degree 9 can be 10-totally-colored.