Concatenating bipartite graphs by Chudnovsky, M, Hompe, P, Scott, A, Seymour, P, Spirkl, S

The chromatic profile of locally bipartite graphs by Illingworth, F

“…Here we study the chromatic profile of locally bipartite graphs. We show that every <i>n</i>-vertex locally bipartite graph with minimum degree greater than 4/7 · <i>n</i> is 3-colourable (4/7 is tight) and with minimum degree greater than 6/11 · <i>n</i> is 4-colourable. …”

Bipartite graphs with no K6 minor by Chudnovsky, M, Scott, A, Seymour, P, Spirkl, S

“…<br> But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every ε > 0 there are arbitrarily large bipartite graphs with average degree at least 8 − ε and no K6 minor. …”

Bayesian nonparametric models for bipartite graphs by Caron, F

“…We develop a novel Bayesian nonparametric model for random bipartite graphs. The model is based on the theory of completely random measures and is able to handle a potentially infinite number of nodes. …”

Book drawings of complete bipartite graphs by de Klerk, E, Pasechnik, D, Salazar, G

Pure pairs. IV. Trees in bipartite graphs by Scott, AD, Seymour, P, Spirkl, S

Risk in a large claims insurance market with bipartite graph structure by Reinert, G, Kley, O, Klueppelberg, C

“…We model the influence of sharing large exogeneous losses to the reinsurance market by a bipartite graph. Using Pareto-tailed claims and multivariate regular variation we obtain asymptotic results for the Value-atRisk and the Conditional Tail Expectation. …”

A note on induced Turán numbers by Illingworth, F

“…Their and subsequent work has focussed on $F$ being a complete bipartite graph. In this short note, we complement this focus by asymptotically determining the induced Turán number whenever $H$ is not bipartite and $F$ is not an independent set nor a complete bipartite graph.…”

On the extremal number of subdivisions by Conlon, D, Lee, J

“…More precisely, we show that if H is a C4-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and Cn3/2−δ edges contains a copy of H⁠. …”

A complexity trichotomy for approximately counting list H-colourings by Galanis, A, Goldberg, L, Jerrum, M

“…If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. …”

On a problem of El-Zahar and Erdős by Nguyen, T, Scott, A, Seymour, P

“…This, together with excluding <i>K_t</i>, is <i>not</i> enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding <i>K_t</i> we exclude the complete bipartite graph <i>K_t,t</i>. More exactly: for all <i>t</i>, <i>c</i> ≥ 1 there exists <i>d</i> ≥ 1 such that if <i>G</i> has minimum degree at least <i>d</i>, and does not contain the complete bipartite graph <i>K_t,t</i> as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least <i>c</i>.…”

Polynomial bounds for chromatic number. I: excluding a biclique and an induced tree by Scott, A, Seymour, P, Spirkl, S

“…It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph $K_{t,t}$ as a subgraph, have bounded chromatic number. …”

Conditional risk measures in a bipartite market structure by Kley, O, Klueppelberg, C, Reinert, G

“…We model the influence of sharing large exogeneous losses to the financial or (re)insurance market by a bipartite graph. Using Pareto-tailed losses and multivariate regular variation, we obtain asymptotic results for conditional risk measures based on the Value-at-Risk and the Conditional Tail Expectation. …”

Clique covers of H-free graphs by Nguyen, T, Scott, A, Seymour, P, Thomassé, S

“…It takes <i>n</i>²/4 cliques to cover all the edges of a complete bipartite graph <i>K</i>_{<i>n/2,n/2</i>}, but how many cliques does it take to cover all the edges of a graph <i>G</i> if <i>G</i> has no <i>K</i>_<i>t,t</i> induced subgraph? …”

Approximately counting H-colourings is BIS-Hard by Galanis, A, Goldberg, L, Jerrum, M

“…We show that for any fixed graph <em>H</em> without trivial components, this is as hard as the well-known problem #BIS, the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in an important complexity class for approximate counting, and is believed not to have an FPRAS. …”

Duality and optimality of auctions for uniform distributions by Giannakopoulos, Y, Koutsoupias, E

“…The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. We demonstrate the power of the framework by applying it to a multiple-good monopoly setting where the buyer has uniformly distributed valuations for the items, the canonical long-standing open problem in the area. …”

Some advances on Sidorenko's conjecture by Conlon, D, Kim, J, Lee, C, Lee, J

“…In this paper, we provide three distinct families of bipartite graphs that have Sidorenko's property. First, using branching random walks, we develop an embedding algorithm which allows us to prove that bipartite graphs admitting a certain type of tree decomposition have Sidorenko's property. …”

Approximately counting H-colourings is #BIS-hard by Galanis, A, Goldberg, L, Jerrum, M

“…We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in a important complexity class for approximate counting, and is believed not to have an FPRAS. …”

Duality and optimality of auctions for uniform distributions by Giannakopoulos, Y, Koutsoupias, E

“…The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. We demonstrate the power of the framework by applying it to a multiple-good monopoly setting where the buyer has uniformly distributed valuations for the items, the canonical long-standing open problem in the area. …”

The complexity of counting locally maximal satisfying assignments of Boolean CSPs by Goldberg, L, Jerrum, M

“…This finding contrasts with the recent discovery that approximately counting locally maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.…”