Search

Given a bipartite graph H = (V = VA ∪ VB, E) in which any vertex in VA (resp., VB) has degree at most DA (resp., DB), suppose there is a partition of V that is a refinement of the bipartition VA ∪ VB such that the parts in VA (resp., VB) have size at least KA (resp., kB). We prove that the condition DA/kB + DB/kA ≤ 1 is sufficient for the existence of an independent set of vertices of H that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos. [ABSTRACT FROM AUTHOR]

We completely characterize the triangulations of the projective plane that admit a spanning bipartite quadrangulation subgraph. This is an affirmative answer to a question by Kündgen and Ramamurthi [J. Combin. Theory Ser. B, 85 (2002), pp. 307-337] for the projective planar case. [ABSTRACT FROM AUTHOR]

A graph G is called C2k+1-free if it does not contain any cycle of length 2k + 1. In 1962, Erdös (together with Gallai), and independently Andrásfai, proved that every n-vertex triangle-free graph with more than (n-1)²/4 + 1 edges is bipartite. In this paper, we extend their result and show that for 1 ≤ t 2k - 2 and 2 ≥ 318²k, every n-vertex C2k+1-free graph with more than (n-t-1)²/4 + (t+2) edges can be made bipartite by either deleting at most t - 1 vertices or deleting at most (⌊t-2⌋/2) + (⌈t+2⌉/2) - 1 edges. The construction shows that this is best possible. [ABSTRACT FROM AUTHOR]

Let G = (A ∪ B, E) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching M in G is a popular max-matching if there is no maximum matching more popular than M. In other words, for any maximum matching N, the number of nodes that prefer M to N is at least the number of nodes that prefer N to M. It is known that popular max-matchings always exist in G and one such matching can be efficiently computed. In this paper we are in the weighted setting, i.e., there is a cost function c : E → R, and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching. [ABSTRACT FROM AUTHOR]

We construct explicit combinatorial Bernoulli factories for the following class of flowbased polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and k-flows. In the process, we uncover new connections to algebraic combinatorics. [ABSTRACT FROM AUTHOR]

We correct an error in the appendix of [N. Alon et al., SIAM J. Discrete Math., 34 (2020), pp. 885-903] and prove that it is NP-hard to approximate the size of a maximum induced matching of a bipartite graph within any constant factor. [ABSTRACT FROM AUTHOR]

The celebrated dependent random choice lemma states that in a bipartite graph, an average vertex (weighted by its degree) has the property that almost all small subsets S in its neighborhood have a common neighborhood almost as large as in the random graph of the same edge-density. There are two well-known applications of this lemma. The first is a theorem of F\"uredi [Combinatorica, 11 (1991), pp. 75--79] and Alon, Krivelevich, and Sudakov [Combin. Probab. Comput., 12 (2003), pp. 477--494] showing that the maximum number of edges in an n-vertex graph not containing a fixed bipartite graph with maximum degree at most r on one side is O(n2-1/r). This was recently extended by Grzesik, Janzer, and Nagy [J. Combin. Theory Ser. B, 156 (2022), pp. 299--309] to the family of so-called (r, t)-blowups of a tree. A second application is a theorem of Conlon, Fox, and Sudakov [Geom. Funct. Anal., 20 (2010), pp. 1354--1366], confirming a special case of a conjecture of Erd\H os and Simonovits and of Sidorenko, showing that if H is a bipartite graph that contains a vertex that is completely joined to the other part and G is a graph, then the probability that the uniform random mapping from V (H) to V (G) is a homomorphism is at least.... In this paper, we introduce a nested variant of the dependent random choice lemma, which might be of independent interest. We then apply it to obtain a common extension of the theorem of Conlon, Fox, and Sudakov and the theorem of Grzesik, Janzer, and Nagy regarding Tur\'an and Sidorenko properties of so-called tree-degenerate graphs. [ABSTRACT FROM AUTHOR]

Thomassen [J. Combin. Theory Ser. B, 141 (2020), pp. 343--351] asked whether every r-edge-connected r-regular graph of even order has r 2 pairwise disjoint perfect matchings. We show that this is not the case if r = 2 mod 4. Together with a recent result of Mattiolo and Steffen [J. Graph Theory, 99 (2022), pp. 107--116] this solves Thomassen's problem for all even r. It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan--Raspaud conjecture, the Berge--Fulkerson conjecture, and the 5-cycle double cover conjecture. [ABSTRACT FROM AUTHOR]

Let Θk1,...,kℓ denote the generalized theta graph, which consists of ℓ internally disjoint paths with lengths k1,...,kℓ, connecting two fixed vertices. We estimate the corresponding extremal number ex(n,Θk1,...,kℓ). When the lengths of all paths have the same parity and at most one path has length 1, ex(n,Θk1,...,kℓ) is O(n1+1/k*), where 2k∗ is the length of the smallest cycle in Θk1,...,kℓ. We also establish matching lower bound in the particular case of ex(n,Θ3,5,5). [ABSTRACT FROM AUTHOR]

A circular r-coloring of a signed graph (G,σ) is an assignment ϕ of points of a circle Cr of circumference r to the vertices of (G,σ) such that for each positive edge uv of (G,σ) the distance of ϕ(v) and ϕ(v) is at least 1 and for each negative edge uv the distance of ϕ(u) from the antipodal of ϕ(v) is at least 1. The circular chromatic number of (G,σ), denoted χc(G,σ), is the infimum of r such that (G,σ) admits a circular r-coloring. This notion is recently defined by Naserasr, Wang, and Zhu who, among other results, proved that for any signed d-degenerate simple graph G^ we have χc(G^)≤2d. For d≥3, examples of signed d-degenerate simple graphs of circular chromatic number 2d are provided. But for d=2 only examples of signed 2-degenerate simple graphs of circular chromatic number close enough to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If (G,σ) is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then χc(G,σ)≤165. Motivated by this observation, we provide an improved upper bound of 4-2⌊n+12⌋ for the circular chromatic number of a signed 2-degenerate simple graph on n vertices and an improved upper bound of 4-4⌊n+22⌋ for the circular chromatic number of a signed bipartite planar simple graph on n vertices. We then show that each of the bounds is tight for any value of n≥4. [ABSTRACT FROM AUTHOR]

Denote by qn (G) the smallest eigenvalue of the signless Laplacian matrix of an n-vertex graph G. Brandt conjectured in 1997 that for regular triangle-free graphs qn(G) =4n/25 · We prove a stronger result: If G is a triangle-free graph, then qn(G) = 15n/94 < 4n/25 Brandt's conjecture is a subproblem of two famous conjectures of Erdőos: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size [n\2] spanning at most n²/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n²/25 edges. In our proof we use linear algebraic methods to upper bound qn(G) 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. [ABSTRACT FROM AUTHOR]

Recently, the saturation problem of 0-1 matrices has gained a lot of attention. This problem can be regarded as a saturation problem of ordered bipartite graphs. Motivated by this, we initiate the study of the saturation problem of ordered and cyclically ordered graphs. We prove that dichotomy also holds in these two cases, i.e., for a (cyclically) ordered graph its saturation function is either bounded or linear. We also determine the order of magnitude for large classes of (cyclically) ordered graphs, giving infinitely many examples exhibiting both possible behaviors, answering a problem of P\'alv\"olgyi. In particular, in the ordered case we define a natural subclass of ordered matchings, the class of linked matchings, and we start their systematic study, concentrating on linked matchings with at most three links and prove that many of them have bounded saturation function. In both the ordered and cyclically ordered case we also consider the semisaturation problem, where dichotomy holds as well and we can even fully characterize the graphs that have bounded semisaturation function. [ABSTRACT FROM AUTHOR]

Let b(k,ℓ,θ) be the maximum number of vertices of valency k in a (k,ℓ) -semiregular bipartite graph with second-largest eigenvalue θ. We obtain an upper bound for b(k,ℓ,θ) for ..... This bound is tight when there exists a distance-biregular graph with particular parameters, and we develop the necessary properties of distance-biregular graphs to prove this. [ABSTRACT FROM AUTHOR]

Let D=(V,A) be a digraph of order n. We define the degree of vertex v in D to be dD(v)=d+D(v)+d-D(v), where d+D(v) and d-D(v) are the out-degree and in-degree of v in D, respectively. Let k be a positive integer and let W be any given subset of V with |W|≥2k. In this paper we show that if dD(x)+dD(y)≥3n-3 for all {x,y}⊆W, then for any integer partition |W|=∑ki=1ni with ni≥2 for each i, there are k disjoint cycles containing exactly n1,...,nk vertices of W, respectively. The degree condition dD(x)+dD(y)≥3n-3 is sharp in some sense and this result confirms the conjecture posed by Wang [J. Graph Theory, 34 (2000), pp. 154-162] as a corollary. The result in this paper implies a theorem on cycle-factors containing matchings in bipartite graphs. Further, the special case W=V is a directed version of the Aigner-Brandt theorem on disjoint cycles in graphs. [ABSTRACT FROM AUTHOR]

For two graphs G and H, write G rbw \rightarrow H if G has the property that every proper coloring of its edges yields a rainbow copy of H. We study the thresholds for such so-called anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form G \cup G(n, p), where G is an n-vertex graph with edge-density at least d, and d is a constant that does not depend on n. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property G \cup G(n, p) rbw \rightarrow Ks for every s. In this paper, we show that for s \geq 9 the threshold is n 1/m2(K\lceil s/2\rceil); in fact, our 1-statement is a supersaturation result. This turns out to (almost) be the threshold for s = 8 as well, but for every 4 \leq s \leq 7, the threshold is lower; see our companion paper for more details. Also in this paper, we determine that the threshold for the property G \cup G(n, p) rbw \rightarrow C2\ell 1 is n 2 for every \ell \geq 2; in particular, the threshold does not depend on the length of the cycle C2\ell 1. For even cycles, and in fact any fixed bipartite graph, no random edges are needed at all; that is, G rbw \rightarrow H always holds, whenever G is as above and H is bipartite. [ABSTRACT FROM AUTHOR]

An identifying code C of a graph G is a dominating set of G such that any two distinct vertices of G have distinct closed neighborhoods within C. These codes have been widely studied for over two decades. We give an improvement over all the best known upper bounds, some of which have stood for over 20 years, for identifying codes in trees, proving the upper bound of (n + \ell)/2, where n is the order and \ell is the number of leaves (pendant vertices) of the graph. In addition to being an improvement in size, the new upper bound is also an improvement in generality, as it actually holds for bipartite graphs having no twins (pairs of vertices with the same closed or open neighborhood) of degree 2 or greater. We also show that the bound is tight for an infinite class of graphs and that there are several structurally different families of trees attaining the bound. We then use our bound to derive a tight upper bound of 2n/3 for twin-free bipartite graphs of order n and characterize the extremal examples as 2-corona graphs of bipartite graphs. This is the best possible, as there exist twin-free graphs, and trees with twins, that need n 1 vertices in any of their identifying codes. We also generalize the existing upper bound of 5n/7 for graphs of order n and girth at least 5 when there are no leaves to the upper bound 5n+2\ell 7 when leaves are allowed. This is tight for the 7-cycle C7 and for all stars. [ABSTRACT FROM AUTHOR]

For a graph $G$, $L(G)^t$ is the $t$th power of the line graph of $G$; that is, vertices of $L(G)^t$ are edges of $G$ and two edges $e,f\in E(G)$ are adjacent in $L(G)^t$ if $G$ contains a path with at most $t$ vertices that starts in a vertex of $e$ and ends in a vertex of $f$. The distance-$t$ chromatic index of $G$ is the chromatic number of $L(G)^t$, and a $t$-strong clique in $G$ is a clique in $L(G)^t$. Finding upper bounds for the distance-$t$ chromatic index and $t$-strong clique are problems related to two famous problems: the conjecture of Erdös and Nešetřil concerning the strong chromatic index, and the degree/diameter problem. We prove that the size of a $t$-strong clique in a graph with maximum degree $\Delta$ is at most $1.75\Delta^t+O\left(\Delta^{t-1}\right)$, and for bipartite graphs the upper bound is at most $\Delta^t+O\left(\Delta^{t-1}\right)$. As a corollary, we obtain upper bounds of $1.881\Delta^t +O\left(\Delta^{t-1}\right)$ and $1.9703+O\left(\Delta^{t-1}\right)$ on the distance-$t$ chromatic index of bipartite graphs and general graphs. We also show results for some special classes of graphs: $K_{1,r}$-free graphs and graphs with a large girth. [ABSTRACT FROM AUTHOR]

Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum-cost edge-set to the graph such that the adversary never wins. We show that this problem is equivalent to covering a digraph with nontrivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a log2 n-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general nonnegative weights we give tight upper and lower approximation bounds relative to the directed Steiner forest problem. Additionally, we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical strong connectivity augmentation problem as well as directed Steiner problems. [ABSTRACT FROM AUTHOR]

A t-bar visibility representation of a graph assigns each vertex up to t horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of positive width. The least t such that G has a t-bar visibility representation is the bar visibility number of G, denoted by b(G). For the complete bipartite graph Km,n, the lower bound b(Km,n) > [mn+4/2m+2n] from Euler's formula is well known. We prove that equality holds. [ABSTRACT FROM AUTHOR]

In the list coloring problem for two matroids, we are given matroids M1 = (S, \scrI 1) and M2 = (S, \scrI 2) on the same ground set S, and the goal is to determine the smallest number k such that, given arbitrary lists Ls of k colors for s \in S, it is possible to choose a color from each list so that every monochromatic set is independent in both M1 and M2. When both M1 and M2 are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant c such that if the coloring number is k (i.e., the ground set can be partitioned into k common independent sets), then the list coloring number is at most c \cdot k. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if M = (S, \scrI) is a matroid in which S can be partitioned into k independent sets, then there exists a partition matroid N = (S,\scrJ) with \scrJ \subseteq \scrI in which S can be partitioned into (A) k independent sets if M is a transversal matroid, (B) 2k 1 independent sets if M is a graphic matroid, (C) \lceil kr/(r 1)\rceil independent sets if M is a paving matroid of rank r, and (D) 2k 2 independent sets if M is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of N is the same as that of M. We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one. [ABSTRACT FROM AUTHOR]

The Fano plane is the unique linear 3-uniform hypergraph on seven vertices and seven hyperedges. It is known that, for all n\geq 8, the balanced complete bipartite 3-uniform hypergraph on n vertices, denoted by Bn, is the 3-uniform hypergraph on n vertices with the largest number of hyperedges that does not contain a copy of the Fano plane. For sufficiently large r and n, we show that Bn admits the largest number of r-edge colorings with no rainbow copy of the Fano plane. [ABSTRACT FROM AUTHOR]

Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chv'atal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milaniv c [J. Discrete Algorithms, 6 (2008), pp. 595--604]. [ABSTRACT FROM AUTHOR]

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in Theta (log chi (G)), while for 3D the minimum scan time is not upper bounded by chi (G). We use this relationship to prove that the existence of a constant-factor approximation implies P = NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of 3/2, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an O(c)-approximation for k-colored graphs with k leq chi (G)c. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph. [ABSTRACT FROM AUTHOR]

This paper considers an edge minimization problem in saturated bipartite graphs. An n by n bipartite graph G is H-saturated if G does not contain a subgraph isomorphic to H but adding any missing edge to G creates a copy of H. More than half a century ago, Wessel and Bollob'as independently solved the problem of minimizing the number of edges in K(s,t)-saturated graphs, where K(s,t) is the "ordered"" complete bipartite graph with s vertices from the first color class and t from the second. However, the very natural "unordered"" analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When s = t, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Kor'andi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in K(s,t)-saturated n by n bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for s = t 1 with the classification of the extremal graphs. We also improve the estimates of Gan, Kor'andi, and Sudakov for general s and t, and for all sufficiently large n. [ABSTRACT FROM AUTHOR]

We consider the following question. We have a dense regular graph G with degree n, where > 0 is a constant. We add m = o(n2) random edges. The edges of the augmented graph G(m) are given independent edge weights X(e); e 2 E(G(m)). We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph but scaled by a factor -1. We consider spanning trees, shortest paths, and perfect matchings in (pseudorandom) bipartite graphs. [ABSTRACT FROM AUTHOR]

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 Kt,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 Hos--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 (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. [ABSTRACT FROM AUTHOR]

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular, we show that in every cover of a Young diagram with bigl(2k k bigr) steps with generalized rectangles, there is a row or a column in the diagram that is used by at least k + 1 rectangles and prove that this is best possible. This answers two questions by Kim et al. [European J. Combin., 86 (2020), 103074], namely, what is the local complete bipartite covering number of a difference graph, and is there a sequence of graphs with a constant local difference graph covering numbers and unbounded local complete bipartite covering numbers? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim et al., we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height 2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension (1 + o(1)) log2 log2 n. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension. [ABSTRACT FROM AUTHOR]

We prove that every bipartite graph of sufficiently large average degree has either a Kt,t-subgraph or an induced subgraph of average degree at least t and girth at least 6. We conjecture that "6"" can be replaced by any constant "k,"" which strengthens a conjecture of Thomassen. In support of this conjecture, we show that it holds for regular graphs. [ABSTRACT FROM AUTHOR]

A class scrF of graphs has the induced ErdH os--Posa property if there exists a function f such that for every graph G and every positive integer k, G contains either k pairwise vertex-disjoint induced subgraphs that belong to scrF, or a vertex set of size at most f(k) hitting all induced copies of graphs in scrF. Kim and Kwon in [J. Combin. Theory Ser. B, 145 (2020), pp. 65--112] showed that for a cycle Cell of length ell, the class of Cell -subdivisions has the induced ErdH os-Posa property if and only if ell leq 4. In this paper, we investigate whether or not the class of H-subdivisions has the induced ErdH os--P'osa property for other graphs H. We completely settle the case when H is a forest or a complete bipartite graph. Regarding the general case, we identify necessary conditions on H for the class of H-subdivisions to have the induced ErdH os-P'osa property. For this, we provide three basic constructions that are useful for proving that the class of the subdivisions of a graph does not have the induced ErdH os-Posa property. Among remaining graphs, we prove that if H is the diamond, the 1-pan, or the 2-pan, then the class of H-subdivisions has the induced Erd Hos-P'osa property. [ABSTRACT FROM AUTHOR]

We interpret realizations of a graph on the sphere up to rotations as elements of a moduli space of curves of genus zero. We focus on those graphs that admit an assignment of edge lengths on the sphere resulting in a flexible object. Our interpretation of realizations allows us to provide a combinatorial characterization of these graphs in terms of the existence of particular colorings of the edges. Moreover, we determine necessary relations for flexibility between the spherical lengths of the edges. We conclude by classifying all possible motions on the sphere of the complete bipartite graph with 3+3 vertices where no two vertices coincide or are antipodal. [ABSTRACT FROM AUTHOR]

This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy rarely leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal. We specifically study graphs that have an ordering avoiding some ordered structures. More precisely, we consider structures that we call patterns on three nodes, and we study the complexity of recognizing the classes associated with such patterns. In this domain, there are three key previous works. Independently Skrien [J. Graph Theory, 6 (1982), pp. 309-316] and Damashke [Forbidden ordered subgraphs, in Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 219--229] noted that several graph classes, such as chordal, bipartite, interval, and comparability graphs, have a characterization in terms of forbidden patterns. On the algorithmic side, Hell, Mohar, and Rafiey [Ordering without forbidden patterns, in Algorithms--ESA 2014, Springer, 2014, pp. 554--565] proved that any class defined by a set of forbidden patterns on three nodes can be recognized in time O(n3) by using an algorithm based on an extension of 2-SAT. We improve on these two lines of works by systematically characterizing all the classes defined by sets of forbidden patterns (on three nodes) and proving that among the 22 different classes (up to complement) that we find, 20 can actually be recognized in linear time. Beyond these results, we consider that this type of characterization is very useful from an algorithmic perspective, leads to a rich structure of classes, and generates many algorithmic and structural open questions worth investigating. [ABSTRACT FROM AUTHOR]

A matrix is homogeneous if all of its entries are equal. Let P be a 2 times 2 zero-one matrix that is not homogeneous. We prove that if an n times n zero-one matrix A does not contain P as a submatrix, then A has a cn times cn homogeneous submatrix for a suitable constant c > 0. We further provide an almost complete characterization of the matrices P (missing only finitely many cases) such that forbidding P in A guarantees an n1 o(1) times n1 o(1) homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs. [ABSTRACT FROM AUTHOR]

We propose bipartite analogues of comparability and cocomparability graphs. Surprisingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids; this is analogous to Gallai’s structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval graphs. [ABSTRACT FROM AUTHOR]

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn [Repeated Patterns in Proper Colourings, preprint, https://arxiv.org/abs/2002.00921 (2020)]. Given a graph H and an integer k ≥ 2, let fk(n, H) be the smallest number of colors c such that there exists a proper edge coloring of the complete graph Kn with c colors containing no k vertex-disjoint color-isomorphic copies of H. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge coloring of Kn and show that fk(n, C4) = θ(n) when k ≥ 3 and n→∞. The methods we used in the edge coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs G and H, let r(G, H, q) be the minimum number of edge colors (not necessarily proper) of G, such that the edges of every copy of H ≤ G together receive at least q distinct colors. Establishing the relation to the Tur\'an number of specified bipartite graphs, we obtain some general lower bounds for r(Kn,n, Ks,t, q) with a broad range of q [ABSTRACT FROM AUTHOR]

A multigraph G is near-bipartite if V (G) can be partitioned as I, F such that I is an independent set and F induces a forest. We prove that a multigraph G is near-bipartite when 3|W| - 2|E(G[W])| ≥ 1 for every W ⊆ V (G), and G contains no K4 and no Moser spindle. We prove that a simple graph G is near-bipartite when 8|W| -5| E(G[W])| ≥ - 4 for every W ⊆ V (G), and G contains no subgraph from some finite family H. We also construct infinite families to show that both results are the best possible in a very sharp sense. [ABSTRACT FROM AUTHOR]

We consider the problem of determining the maximal 2 (0; 1] such that every matching M of size k (or at most k) in a bipartite graph G contains an induced matching of size at least jMj. This measure was recently introduced in [N. Alon et al., Adv. Neural Inf. Process. Syst., 2017, pp. 2097{2106] and is motivated by computational models in cognitive neuroscience as well as by modeling interference in radio and communication networks. We prove various hardness results for computing either exactly or approximately. En route to our results, we also consider the maximum connected matching problem: determining the largest matching N in a graph G such that every two edges in N are connected by an edge. We prove a nearly optimal n1?" hardness of approximation result (under randomized reductions) for connected matching in bipartite graphs (with both sides of cardinality n). Toward this end we define bipartite half-covers: a new combinatorial object that may be of independent interest. To our knowledge, the best previous hardness result for the maximum connected matching problem was that it is hard to approximate within some constant > 1. Finally, we demonstrate the existence of bipartite graphs with n vertices on each side of average degree d, achieving = 1=2 " for matchings of size sufficiently smaller than n=d. This nearly matches the trivial upper bound of 1=2 on which holds for any graph containing a path of length 3. [ABSTRACT FROM AUTHOR]

Given a graph H, the Tur'an number ex(n,H) is the largest number of edges in an Hfree graph on n vertices. We make progress on a recent conjecture of Conlon, Janzer, and Lee [More on the Extremal Number of Subdivisions, arXiv:1903.10631v1, 2019] on the Tur'an numbers of bipartite graphs, which in turn yields further progress on a conjecture of Erdos and Simonovits [Combinatorica, 1 (1981), pp. 25-42]. Let s, t, k = 2 be integers. Let Kk s,t denote the graph obtained from the complete bipartite graph Ks,t by replacing each edge uv in it with a path of length k between u and v such that the st replacing paths are internally disjoint. It follows from a general theorem of Bukh and Conlon [J. Eur. Math. Soc. (JEMS), 20 (2018), pp. 1747-1757] that ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Conlon, Janzer, and Lee recently conjectured that for any integers s, t, k = 2, ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Among many other things, they settled the k = 2 case of their conjecture. As the main result of this paper, we prove their conjecture for k = 3, 4. Our main results also yield infinitely many new so-called Tur'an exponents: rationals r ? (1, 2) for which there exists a bipartite graph H with ex(n,H) = T(nr), adding to the lists recently obtained by Jiang, Ma, and Yepremyan [On Tur'an Exponents of Bipartite Graphs, arXiv:1806.02838, 2018], by Kang, Kim, and Liu [On the Rational Tur'an Exponent Conjecture, arXiv:1811.06916, 2018], and by Conlon, Janzer, and Lee. Our method builds on an extension of the Conlon-Janzer-Lee method. We also note that the extended method also gives a weaker version of the Conlon-Janzer-Lee conjecture for all k = 2. [ABSTRACT FROM AUTHOR]

For a graph F, the k-subdivision of F, denoted Fk, is the graph obtained by replacing the edges of F with internally vertex-disjoint paths of length k. In this paper, we prove that ex(n,Kk s,t) = O(n1+ s 1 sk), which is tight for t sufficiently large. This settles a conjecture of Conlon-- Janzer--Lee, and improves on a substantial body of work by Conlon--Janzer--Lee and Jiang--Qiu. [ABSTRACT FROM AUTHOR]

Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming strong duality into combinatorial min-max theorems. The definition of a linear inequality system being totally dual integral (TDI) revolves around the existence of optimal dual solutions that are integral and thus naturally applies to a host of combinatorial optimization problems that are cast as integer programs whose linear program (LP) relaxations have the TDIness property. However, when combinatorial problems are formulated using more general convex relaxations, such as semidefinite programs (SDPs), it is not at all clear what an appropriate notion of integrality in the dual program is, thus inhibiting the generalization of the theory to more general forms of structured convex optimization. (In fact, we argue that the rank-one constraint usually added to SDP relaxations is not adequate in the dual SDP.) In this paper, we propose a notion of total dual integrality for SDPs that generalizes the notion for LPs, by relying on an "integrality constraint" for SDPs that is primal-dual symmetric. A key ingredient for the theory is a generalization to compact convex sets of a result of Hoffman for polytopes, fundamental for generalizing the polyhedral notion of total dual integrality introduced by Edmonds and Giles. We study the corresponding theory applied to SDP formulations for stable sets in graphs using the Lovâsz theta function and show that total dual integrality in this case corresponds to the underlying graph being perfect. We also relate dual integrality of an SDP formulation for the maximum cut problem to bipartite graphs. Total dual integrality for extended formulations naturally comes into play in this context. [ABSTRACT FROM AUTHOR]

An edge coloring of a graph G is a Gallai coloring if it contains no rainbow triangle. We show that the number of Gallai r-colorings of Kn is (\bigl(r 2\bigr) + o(1))2\Bigl(n 2\Bigr). This result indicates that almost all Gallai r-colorings of Kn use only 2 colors. We also study the extremal behavior of Gallai r-colorings among all n-vertex graphs. We prove that the complete graph Kn admits the largest number of Gallai 3-colorings among all n-vertex graphs when n is sufficiently large, while for r\geq 4, it is the complete bipartite graph K\lfloor n/2\rfloor,\lceil n/2\rceil. Our main approach is based on the hypergraph container method, developed independently by Balogh, Morris, and Samotij as well as by Saxton and Thomason, together with some stability results. [ABSTRACT FROM AUTHOR]

The representation complexity of a bipartite graph G = (P;Q) is the minimum size s i=1(jAij + jBij) over all possible ways to write G as a (not necessarily disjoint) union of complete bipartite subgraphs G = [si =1Ai = Bi where Ai = P;Bi = Q for i = 1;:::; s. In this paper we prove that if G is semialgebraic, i.e., when P is a set of m points in Rd1, Q is a set of n points in Rd2, and the edges are defined by some semialgebraic relations, the representation complexity of G is O(m d1d2-d2 d1d2-1 +" n d1d2-d1 d1d2-1 +" + m1+" + n1+") for arbitrarily small positive ". This generalizes results by Apfelbaum{Sharir and Solomon{Sharir. As a consequence, when G is Ku;u-free for some positive integer u, its number of edges is O(um d1d2-d2 d1d2-1 +" n d1d2-d1 d1d2-1 +" + um1+" + un1+"). This bound is stronger than a result of Fox, Pach, Sheffer, Suk, and Zahl when the first term dominates and u grows with m; n. Another consequence is that we can find a large complete bipartite subgraph in a semialgebraic graph when the number of edges is large. Similar results hold for semialgebraic hypergraphs. [ABSTRACT FROM AUTHOR]

Borrowing L\'aszl\'o Sz\'ekely'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(Kn) of the complete graph Kn is H(n) := 1 4 \lfloor n 2 \rfloor \lfloor n 1 2 \rfloor \lfloor n 2 2 \rfloor \lfloor n 3 2 \rfloor for all n \geq 3. This has been verified only for n \leq 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(Kn) > 0.905H(n). Also using this framework, we prove that asymptotically cr(Kn) is at least 0.985H(n). We also show that the spherical geodesic crossing number of Kn is asymptotically at least 0.996H(n). [ABSTRACT FROM AUTHOR]

We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of all matchings, extended by a binary entry indicating whether the matching contains two specific edges. This polytope is associated with the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein [Combinatorial Optimization with One Quadratic Term, Ph.D. thesis, TU Dortmund, Dortmund, Germany]. In addition, we also derive facetness and separation results for the polytopes. The completeness proof is based on a geometric relationship to a matching polytope of a nonbipartite graph. Using standard techniques, we finally extend the result to capacitated 6-matchings. [ABSTRACT FROM AUTHOR]

A subset S of initially infected vertices of a graph G is called zero forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbor, infects this neighbor. The zero forcing number of G is the minimum cardinality of a zero forcing set in G. We study the zero forcing number of various classes of graphs, including graphs of large girth, H-free graphs for a fixed bipartite graph H, and random and pseudorandom graphs. [ABSTRACT FROM AUTHOR]

We estimate the 3-color bipartite Ramsey number for balanced bipartite graphs H with small bandwidth and bounded maximum degree. More precisely, we show that the minimum value of N such that in any 3-edge coloring of KN,N there is a monochromatic copy of H is at most (3/2+o(1))|V (H)|. In particular, we determine asymptotically the 3-color bipartite Ramsey number for grid graphs. [ABSTRACT FROM AUTHOR]

Every graph G can be represented by a collection of equi-radii spheres in a ddimensional metric ΔDelta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in ΔDelta is called the sphericity of G, and if the collection of spheres are nonoverlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact-dimension of the complete bipartite graph Kn,n in various Lp-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems. [ABSTRACT FROM AUTHOR]

We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2 + O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2 + O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2n/2) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments, and bipartite graphs. [ABSTRACT FROM AUTHOR]

conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry and are well studied in graph theory. Here we study the natural problem of the conflict-free chromatic number Xchi CF (G) (the smallest k for which conflict-free k-colorings exist). We provide results both for closed neighborhoods N[v], for which a vertex v is a member of its neighborhood, and for open neighborhoods N(v), for which vertex v is not a member of its neighborhood. For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph G does not contain Kk+1 as a minor, then Xchi CF (G) ≤ k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, while for outerplanar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with two colors, while for outerplanar graphs, two colors always suffice. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k € { 1, 2, 3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. Moreover, we establish that any general planar graph has a conflict-free coloring with at most eight colors. [ABSTRACT FROM AUTHOR]

Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [Combin. Probab. Comput., 15 (2006), pp. 815--822] showed that on ℤd, the single vertex discrepancy is only a constant cd. Other authors also determined the precise value of cd for d = 1, 2. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph Zd. We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions d ≥ 1 and arbitrary discrepancies l ≥ 0, we construct configurations that reach a discrepancy of at least l. [ABSTRACT FROM AUTHOR]

Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-colored by n colors with at least n + 1 edges of each color there must be a matching that uses each color exactly once. In this paper we consider the same question without the bipartiteness assumption. We show that in any multigraph with edge multiplicities o(n) that is properly edgecolored by n colors with at least n+o(n) edges of each color there must be a matching of size n-O(1) that uses each color at most once. [ABSTRACT FROM AUTHOR]