Search

An edge e of a matching covered graph G is removable if G−e is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. A nonbipartite matching covered graph G is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi and Murty proved that every brick other than K4 and C6¯ has at least Δ−2 removable edges. A brick G is near‐bipartite if it has a pair of edges {e1,e2} such that G−{e1,e2} is a bipartite matching covered graph. In this paper, we show that in a near‐bipartite brick G with at least six vertices, every vertex of G, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, G has at least |V(G)|−62 removable edges. Moreover, all graphs attaining this lower bound are characterized. [ABSTRACT FROM AUTHOR]

For f:R2→R, let ΓR(f) be a two‐dimensional algebraically defined graph, that is, a bipartite graph where each partite set is a copy of R2 and two vertices (a,a2) and [x,x2] are adjacent if and only if a2+x2=f(a,x). It is known that ΓR(XY) has girth 6 and can be extended to the point‐line incidence graph of the classical real projective plane. However, it was unknown whether there exists f∈R[X,Y] such that ΓR(f) has girth 6 and is nonisomorphic to ΓR(XY). This paper answers this question affirmatively and thus provides a construction of a nonclassical real projective plane. This paper also studies the diameter and girth of ΓR(f) for families of bivariate functions f. [ABSTRACT FROM AUTHOR]

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let qB(G) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider qB(G) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ=Δ(G) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that qB(G)≤2Δ+8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, qB(G)≤2Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and qB(G)≤Δ+1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ≥4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, qB(G)≤2Δ(G) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and qB(G)≤Δ(G) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

For a vertex set X $X$ in a graph, the edge cut∂(X) $\partial (X)$ is the set of edges with exactly one end vertex in X $X$. An edge cut ∂(X) $\partial (X)$ is tight if every perfect matching of the graph contains exactly one edge in ∂(X) $\partial (X)$. A matching covered bipartite graph G $G$ is a brace if, for every tight cut ∂(X) $\partial (X)$, |X|=1 $|X|=1$ or |X¯|=1 $|\bar{X}|=1$, where X¯=V(G)⧹X $\bar{X}=V(G)\setminus X$. Braces play an important role in Lovász's tight cut decomposition of matching covered graphs. The bicontraction of a vertex v $v$ of degree two in a graph, with precisely two neighbours v1 ${v}_{1}$ and v2 ${v}_{2}$, consists of shrinking the set {v1,v,v2} $\{{v}_{1},v,{v}_{2}\}$ to a single vertex. The retract of a matching covered graph G $G$ is the graph obtained from G $G$ by repeatedly the bicontractions of vertices of degree two. An edge e $e$ of a brace G $G$ with at least six vertices is thin if the retract of G−e $G-e$ is a brace. McCuaig showed that every brace of order at least six has a thin edge. In a brace G $G$ of order six or more, Carvalho, Lucchesi and Murty proved that G $G$ has two thin edges, and conjectured that G $G$ contains two nonadjacent thin edges. Further, they made a stronger conjecture: There exists a positive constant c $c$ such that every brace G $G$ has c|V(G)| $c|V(G)|$ thin edges. By showing that, in every cubic brace G $G$ of order at least six, there exists a matching M $M$ of size at least |V(G)|∕10 $|V(G)|\unicode{x02215}10$ such that every edge in M $M$ is thin, we prove that the above two conjectures hold for cubic braces. [ABSTRACT FROM AUTHOR]

Given two graphs G,H $G,H$ and a positive integer q $q$, an (H,q) $(H,q)$‐coloring of G $G$ is an edge‐coloring of G $G$ such that every copy of H $H$ in G $G$ receives at least q $q$ distinct colors. The bipartite Erdős–Gyárfás function r(Kn,n,Ks,t,q) $r({K}_{n,n},{K}_{s,t},q)$ is defined to be the minimum number of colors needed for Kn,n ${K}_{n,n}$ to have a (Ks,t,q) $({K}_{s,t},q)$‐coloring. For balanced complete bipartite graphs Kp,p ${K}_{p,p}$, the function r(Kn,n,Kp,p,q) $r({K}_{n,n},{K}_{p,p},q)$ was studied systematically in Axenovich et al. In this paper, we study the asymptotic behavior of this function for complete bipartite graphs Ks,t ${K}_{s,t}$ that are not necessarily balanced. Our main results deal with thresholds and lower and upper bounds for the growth rate of this function, in particular for (sub)linear and (sub)quadratic growth. We also obtain new lower bounds for the balanced bipartite case, and improve several results given by Axenovich, Füredi and Mubayi. Our proof techniques are based on an extension to bipartite graphs of the recently developed Color Energy Method by Pohoata and Sheffer and its refinements, and a generalization of an old result due to Corrádi. [ABSTRACT FROM AUTHOR]

In matching theory, one of the most fundamental and classical branches of combinatorics, canonical decompositions of graphs are powerful and versatile tools that form the basis of this theory. However, the abilities of the known canonical decompositions, that is, the Dulmage–Mendelsohn, Kotzig–Lovász, and Gallai–Edmonds decompositions, are limited because they are only applicable to particular classes of graphs, such as bipartite graphs, or they are too sparse to provide sufficient information. To overcome these limitations, we introduce a new canonical decomposition that is applicable to all graphs and provides much finer information. This decomposition also provides the answer to the longstanding absence of a canonical decomposition that is nontrivially applicable to general graphs with perfect matchings. We focus on the notion of factor‐components as the fundamental building blocks of a graph; through the factor‐components, our new canonical decomposition states how a graph is organized and how it contains all the maximum matchings. The main results that constitute our new theory are the following: (i) a canonical partial order over the set of factor‐components, which describes how a graph is constructed from its factor‐components; (ii) a generalization of the Kotzig–Lovász decomposition, which shows the inner structure of each factor‐component in the context of the entire graph; and (iii) a canonically described interrelationship between (i) and (ii), which integrates these two results into a unified theory of a canonical decomposition. These results are obtained in a self‐contained way, and our proof of the generalized Kotzig–Lovász decomposition contains a shortened and self‐contained proof of the classical counterpart. [ABSTRACT FROM AUTHOR]

PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four. We show that there exist polynomial‐time algorithms for the following classes of graphs: claw‐free, P5 ${P}_{5}$‐free, diameter two, bipartite with diameter three, and graphs with bounded treewidth. [ABSTRACT FROM AUTHOR]

Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose 0≤ϵ≤1, G is a graph, L is a list assignment for G, and r is a function with nonempty domain D⊆V(G) such that r(v)∈L(v) for each v∈D (r is called a request of L). The triple (G,L,r) is ϵ‐satisfiable if there exists a proper L‐coloring f of G such that f(v)=r(v) for at least ϵ∣D∣ vertices in D. We say G is (k,ϵ)‐flexible if (G,L′,r′) is ϵ‐satisfiable whenever L′ is a k‐assignment for G and r′ is a request of L′. It was shown by Dvořák et al. that if d+1 is prime, G is a d‐degenerate graph, and r is a request for G with domain of size 1, then (G,L,r) is 1‐satisfiable whenever L is a (d+1)‐assignment. In this paper, we extend this result to all d for bipartite d‐degenerate graphs. The literature on flexible list coloring tends to focus on showing that for a fixed graph G and k∈N there exists an ϵ>0 such that G is (k,ϵ)‐flexible, but it is natural to try to find the largest possible ϵ for which G is (k,ϵ)‐flexible. In this vein, we improve a result of Dvořák et al., by showing d‐degenerate graphs are (d+2,1∕2d+1)‐flexible. In pursuit of the largest ϵ for which a graph is (k,ϵ)‐flexible, we observe that a graph G is not (k,ϵ)‐flexible for any k if and only if ϵ>1∕ρ(G), where ρ(G) is the Hall ratio of G, and we initiate the study of the list flexibility number of a graphG, which is the smallest k such that G is (k,1∕ρ(G))‐flexible. We study relationships and connections between the list flexibility number, list chromatic number, list packing number, and degeneracy of a graph. [ABSTRACT FROM AUTHOR]

A tree T $T$ is said to be even if all pairs of vertices of degree one in T $T$ are joined by a path of even length. We conjecture that every r $r$‐regular nonbipartite connected graph G $G$ has a spanning even tree and verify this conjecture when G $G$ has a 2‐factor. Well‐known results of Petersen and Hanson et al. imply that the only remaining unsolved case is when r $r$ is odd and G $G$ has at least r $r$ bridges. We investigate this case further and propose some related conjectures. [ABSTRACT FROM AUTHOR]

Given a graph L $L$, the Turán number ex(n,L) $\text{ex}(n,L)$ is the maximum possible number of edges in an n $n$‐vertex L $L$‐free graph. The study of Turán number of graphs is a central topic in extremal graph theory. Although the celebrated Erdős‐Stone‐Simonovits theorem gives the asymptotic value of ex(n,L) $\text{ex}(n,L)$ for nonbipartite L $L$, it is challenging in general to determine the exact value of ex(n,L) $\text{ex}(n,L)$ for χ(L)≥3 $\chi (L)\ge 3$. The odd‐ballooning of H $H$ is a graph such that each edge of H $H$ is replaced by an odd cycle and all new vertices of odd cycles are distinct. Here the length of odd cycles is not necessarily equal. The exact value of Turán number of the odd‐ballooning of H $H$ is previously known for H $H$ being a cycle, a path, a tree with assumptions, and K2,3 ${K}_{2,3}$. In this paper, we manage to obtain the exact value of Turán number of the odd‐ballooning of Ks,t ${K}_{s,t}$ with 2≤s≤t $2\le s\le t$, where (s,t)∉{(2,2),(2,3)} $(s,t)\notin \{(2,2),(2,3)\}$ and each odd cycle has length at least five. [ABSTRACT FROM AUTHOR]

In this paper, the concept of circular r $r$‐flow in a mono‐directed signed graph (G,σ) $(G,\sigma)$ is introduced. That is a pair (D,f) $(D,f)$, where D $D$ is an orientation on G $G$ and f:E(G)→(−r,r) $f:E(G)\to (-r,r)$ satisfies that ∣f(e)∣∈[1,r−1] $| f(e)| \in [1,r-1]$ for each positive edge e $e$ and ∣f(e)∣∈[0,r2−1]∪[r2+1,r) $| f(e)| \in [0,\frac{r}{2}-1]\cup [\frac{r}{2}+1,r)$ for each negative edge e $e$, and the total in‐flow equals the total out‐flow at each vertex. This is the dual notion of circular colorings of signed graphs and is distinct from the concept of circular flows in bi‐directed graphs associated with signed graphs studied in the literature. We first explore the connection between circular 2kk−1 $\frac{2k}{k-1}$‐flows and modulo k $k$‐orientations in signed graphs. Then we focus on the upper bounds for the circular flow indices of signed graphs in terms of the edge‐connectivity, where the circular flow index of a signed graph is the minimum value r $r$ such that it admits a circular r $r$‐flow. We prove that every 3‐edge‐connected signed graph admits a circular 6‐flow and every 4‐edge‐connected signed graph admits a circular 4‐flow. More generally, for k≥2 $k\ge 2$, we show that every (3k−1) $(3k-1)$‐edge‐connected signed graph admits a circular 2kk−1 $\frac{2k}{k-1}$‐flow, every 3k $3k$‐edge‐connected signed graph has a circular r $r$‐flow with r<2kk−1 $r\lt \frac{2k}{k-1}$, and every (3k+1) $(3k+1)$‐edge‐connected signed graph admits a circular 4k+22k−1 $\frac{4k+2}{2k-1}$‐flow. Moreover, the (6k−2) $(6k-2)$‐edge‐connectivity condition is shown to be sufficient for a signed Eulerian graph to admit a circular 4k2k−1 $\frac{4k}{2k-1}$‐flow, and applying this result to planar graphs, we conclude that every signed bipartite planar graph of negative girth at least 6k−2 $6k-2$ admits a homomorphism to the negative even cycles C−2k ${C}_{-2k}$. [ABSTRACT FROM AUTHOR]

We study the minimum number of maximum matchings in a bipartite multigraph G $G$ with parts X $X$ and Y $Y$ under various conditions, refining the well‐known lower bound due to M. Hall. When ∣X∣=n $| X| =n$, every vertex in X $X$ has degree at least k $k$, and every vertex in X $X$ has at least r $r$ distinct neighbors, the minimum is r!(k−r+1) $r!(k-r+1)$ when n≥r $n\ge r$ and is [r+n(k−r)]∏i=1n−1(r−i) $[r+n(k-r)]{\prod }_{i=1}^{n-1}(r-i)$ when n≤r $n\le r$. When every vertex has at least two neighbors and ∣Y∣−∣X∣=t≥0 $| Y| -| X| =t\ge 0$, the minimum is [(n−1)t+2+b](t+1) $[(n-1)t+2+b](t+1)$, where b=∣E(G)∣−2(n+t) $b=| E(G)| -2(n+t)$. We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions. [ABSTRACT FROM AUTHOR]

For positive integers s $s$, t $t$, m $m$ and n $n$, the Zarankiewicz number Zs,t(m,n) ${Z}_{s,t}(m,n)$ is defined to be the maximum number of edges in a bipartite graph with parts of sizes m $m$ and n $n$ that has no complete bipartite subgraph containing s $s$ vertices in the part of size m $m$ and t $t$ vertices in the part of size n $n$. A simple argument shows that, for each t≥2 $t\ge 2$, Z2,t(m,n)=(t−1)m2+n ${Z}_{2,t}(m,n)=(t-1)\left(\genfrac{}{}{0.0pt}{}{m}{2}\right)+n$ when n≥(t−1)m2 $n\ge (t-1)\left(\genfrac{}{}{0.0pt}{}{m}{2}\right)$. Here, for large m $m$, we determine the exact value of Z2,t(m,n) ${Z}_{2,t}(m,n)$ in almost all of the remaining cases where n=Θ(tm2) $n={\rm{\Theta }}(t{m}^{2})$. We establish a new family of upper bounds on Z2,t(m,n) ${Z}_{2,t}(m,n)$ which complement a family already obtained by Roman. We then prove that the floor of the best of these bounds is almost always achieved. We also show that there are cases in which this floor cannot be achieved and others in which determining whether it is achieved is likely a very hard problem. Our results are proved by viewing the problem through the lens of linear hypergraphs and our constructions make use of existing results on edge decompositions of dense graphs. [ABSTRACT FROM AUTHOR]

A matching M $M$ in a graph G $G$ is semistrong if every edge of M $M$ has an endvertex of degree one in the subgraph induced by the vertices of M $M$. A semistrong edge‐coloring of a graph G $G$ is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge‐colorings initiated by Gyárfás and Hubenko. We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge‐coloring which follow from results regarding other, at first sight nonrelated, problems. We conclude the paper with several open problems. [ABSTRACT FROM AUTHOR]

What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the "basic treewidth obstructions"). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called "layered wheels," contain wheels, where a wheel consists of a hole (i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth. [ABSTRACT FROM AUTHOR]

A conjecture proposed by Bermond and Thomassen in 1981 states that every digraph with minimum out‐degree at least 2k−1 $2k-1$ contains k $k$ vertex disjoint directed cycles for any integer k≥1 $k\ge 1$, which has received substantial attention. This conjecture has been confirmed for k≤3 $k\le 3$. In 2014, Lichiardopol raised a very related conjecture that for every integer k≥2 $k\ge 2$, there exists an integer g(k) $g(k)$ such that every digraph with minimum out‐degree at least g(k) $g(k)$ contains k $k$ vertex disjoint directed cycles of different lengths. For a digraph D $D$ and a set of k $k$ vertex disjoint directed cycles C ${\mathscr{C}}$ in D $D$, we denote κk(C) ${\kappa }^{k}({\mathscr{C}})$ to be the maximum number of directed cycles in C ${\mathscr{C}}$ of distinct lengths. Let κk(D)=max{κk(C)∣Cis a set ofkvertexdisjoint directed cycles inD} ${\kappa }^{k}(D)=\max \{{\kappa }^{k}({\mathscr{C}})| {\mathscr{C}}\,\,\text{is a set of}\,\,k\,\text{vertex}\,\text{disjoint directed cycles in}\,\,D\}$. We define κk(D)=0 ${\kappa }^{k}(D)=0$ if D $D$ has no k $k$ vertex disjoint directed cycles. In this paper, we mainly investigate vertex disjoint directed cycles in tournaments and bipartite tournaments. We first show that κk(D)≥2 ${\kappa }^{k}(D)\ge 2$ for every tournament D $D$ with minimum out‐degree at least 2k−1 $2k-1$, where k≥3 $k\ge 3$. We further prove that for k≥1 $k\ge 1$ and γ∈{1,2,...,k} $\gamma \in \{1,2,\ldots ,k\}$, any tournament D $D$ with minimum out‐degree at least γ2−2γ+6k−32 $\frac{{\gamma }^{2}-2\gamma +6k-3}{2}$ satisfies that κk(D)≥γ ${\kappa }^{k}(D)\ge \gamma $. Moreover, we deduce that for any tournament D $D$ with minimum out‐degree at least 7, κ3(D)=3 ${\kappa }^{3}(D)=3$ holds. Additionally, we classify strong bipartite tournaments with minimum out‐degree at least 2k−1 $2k-1$ in which any k $k$ vertex disjoint directed cycles have the same length, where k≥2 $k\ge 2$. That is, for any strong bipartite tournament D $D$ with minimum out‐degree at least 2k−1 $2k-1$, then κk(D)=1 ${\kappa }^{k}(D)=1$ if and only if D $D$ is isomorphic to a member of BT(n1,n2,...,n2k) $BT({n}_{1},{n}_{2},\ldots ,{n}_{2k})$, which is defined in the context. [ABSTRACT FROM AUTHOR]

Let r≥2 $r\ge 2$ and let F $F$ be an (r+1) $(r+1)$ ‐chromatic graph with a color‐critical edge, that is, there exists e∈E(F) $e\in E(F)$ such that F−e $F-e$ has chromatic number r $r$. Gerbner recently conjectured that every n $n$ ‐vertex maximal F $F$ ‐free graph with at least (1−1r)n22−o(nr+1r) $(1-\frac{1}{r})\frac{{n}^{2}}{2}-o({n}^{\frac{r+1}{r}})$ edges contains an induced complete r $r$ ‐partite graph on n−o(n) $n-o(n)$ vertices. Let Fs,k ${F}_{s,k}$ be a graph obtained from s $s$ copies of C2k+1 ${C}_{2k+1}$ by sharing a common edge. In this paper, we show that for all k≥2 $k\ge 2$ if G $G$ is an n $n$ ‐vertex maximal Fs,k ${F}_{s,k}$ ‐free graph with at least n2∕4−o(ns+2s+1) ${n}^{2}\unicode{x02215}4-o({n}^{\frac{s+2}{s+1}})$ edges, then G $G$ contains an induced complete bipartite graph on n−o(n) $n-o(n)$ vertices. We also construct graphs to show that the magnitude in o(ns+2s+1) $o({n}^{\frac{s+2}{s+1}})$ is best possible, which disproves Gerbner's conjecture for r=2 $r=2$. [ABSTRACT FROM AUTHOR]

We present new sharp sufficient conditions for the existence of properly colored and rainbow C4 ${C}_{4}$'s in edge‐colored graphs. Our first results deal with sharp color neighborhood conditions for the existence of properly colored C4 ${C}_{4}$'s in edge‐colored complete graphs and complete bipartite graphs, respectively. Next, we characterize the extremal graphs for an anti‐Ramsey number result due to Alon on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete graphs. We also generalize Alon's result from complete to general edge‐colored graphs. Finally, we derive a structural property regarding the extremal graphs for a bipartite counterpart of Alon's result due to Axenovich, Jiang, and Kündgen on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete bipartite graphs. We also generalize their result from complete to general bipartite edge‐colored graphs. [ABSTRACT FROM AUTHOR]

The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique‐ and rank‐width of graphs, because it is one of the minimal hereditary classes of graphs of unbounded clique‐ and rank‐width. It also contains a number of important subclasses, which are critical with respect to other parameters, such as graph lettericity or shrub‐depth, and with respect to other notions, such as well‐quasi‐ordering or complexity of algorithmic problems. In the present paper we identify critical subclasses of bipartite permutation graphs of various types. [ABSTRACT FROM AUTHOR]

A proper edge‐coloring of a graph is an interval coloring if the labels on the edges incident to any vertex form an interval, that is, form a set of consecutive integers. The interval coloring thickness θ(G) $\theta (G)$ of a graph G $G$ is the smallest number of interval colorable graphs edge‐decomposing G $G$. We prove that θ(G)=o(n) $\theta (G)=o(n)$ for any graph G $G$ on n $n$ vertices. This improves the previously known bound of 2⌈n∕5⌉ $2\lceil n\unicode{x02215}5\rceil $, see Asratian, Casselgren, and Petrosyan. While we do not have a single example of a graph with an interval coloring thickness strictly greater than 2, we construct bipartite graphs whose interval coloring spectrum has arbitrarily many arbitrarily large gaps. Here, an interval coloring spectrum of a graph is the set of all integers t $t$ such that the graph has an interval coloring using t $t$ colors. Interval colorings of bipartite graphs naturally correspond to no‐wait schedules, say for parent–teacher conferences, where a conversation between any teacher and any parent lasts the same amount of time. Our results imply that any such conference with n $n$ participants can be coordinated in o(n) $o(n)$ no‐wait periods. In addition, we show that for any integers t $t$ and T $T$, t

It was conjectured by Ohba, and proved by Noel, Reed and Wu that k $k$‐chromatic graphs G $G$ with ∣V(G)∣≤2k+1 $| V(G)| \le 2k+1$ are chromatic‐choosable. This upper bound on ∣V(G)∣ $| V(G)| $ is tight: if k $k$ is even, then K3⋆(k∕2+1),1⋆(k∕2−1) ${K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$ and K4,2⋆(k−1) ${K}_{4,2\star (k-1)}$ are k $k$‐chromatic graphs with 2k+2 $2k+2$ vertices that are not chromatic‐choosable. It was proved by Zhu and Zhu that these are the only non‐k $k$‐choosable complete k $k$‐partite graphs with 2k+2 $2k+2$ vertices. For G∈{K3⋆(k∕2+1),1⋆(k∕2−1),K4,2⋆(k−1)} $G\in \{{K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)},{K}_{4,2\star (k-1)}\}$, a bad list assignment of G $G$ is a k $k$‐list assignment L $L$ of G $G$ such that G $G$ is not L $L$‐colourable. Bad list assignments for G=K4,2⋆(k−1) $G={K}_{4,2\star (k-1)}$ were characterized by Enomoto, Ohba, Ota and Sakamoto. In this paper, we first give a simpler proof of this result, and then we characterize bad list assignments for G=K3⋆(k∕2+1),1⋆(k∕2−1) $G={K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$. Using these results, we characterize all non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$ vertices. [ABSTRACT FROM AUTHOR]

A homomorphism of a signed graph (G,σ) $(G,\sigma)$ to (H,π) $(H,\pi)$ is a mapping of vertices and edges of G $G$ to (respectively) vertices and edges of H $H$ such that adjacencies, incidences, and the signs of closed walks are preserved. We observe in this work that, for k≥3 $k\ge 3$, the k $k$‐coloring problem of a given graph G $G$ can be captured by homomorphism to (K2k,σm) $({K}_{2k},{\sigma }_{m})$ from a signed bipartite graph that is built from G $G$. Here σm ${\sigma }_{m}$ assigns a negative sign to the edges of a perfect matching and a positive sign to the rest. Motivated by these reformulations and in connection with results on 3‐colorings of planar graphs, such as Grötzsch's theorem, we prove that any signed graph with the maximum average degree strictly less than 145 $\frac{14}{5}$ admits a homomorphism to (K6,σm) $({K}_{6},{\sigma }_{m})$. For k≥4 $k\ge 4$, we show that the maximum average degree being strictly less than 3 would suffice for a signed graph to admit a homomorphism to (K2k,σm) $({K}_{2k},{\sigma }_{m})$. Both of these bounds are tight. We discuss applications of our work to signed planar graphs and its connection to the study of homomorphisms of 2‐edge‐colored graphs. Among a number of interesting questions that are left open, a notable one is a possible extension of Steinberg's conjecture for the class of signed bipartite planar graphs. [ABSTRACT FROM AUTHOR]

Given a finite simple graph G $G$, an odd cover ofG $G$ is a collection of complete bipartite graphs, or bicliques, in which each edge of G $G$ appears in an odd number of bicliques, and each nonedge of G $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of G $G$ by b2(G) ${b}_{2}(G)$ and prove that b2(G) ${b}_{2}(G)$ is bounded below by half of the rank over F2 ${{\mathbb{F}}}_{2}$ of the adjacency matrix of G $G$. We show that this lower bound is tight in the case when G $G$ is a bipartite graph and almost tight when G $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from b2(G) ${b}_{2}(G)$. Babai and Frankl proposed the "odd cover problem," which in our language is equivalent to determining b2(Kn) ${b}_{2}({K}_{n})$. In this paper, we determine that b2(Kn) ${b}_{2}({K}_{n})$ is n∕2 $n\unicode{x02215}2$ when 8∣n $8| n$ and is (n+1)∕2 $(n+1)\unicode{x02215}2$ when n $n$ is equivalent to 1 or −1 $-1$ modulo 8. [ABSTRACT FROM AUTHOR]

The independence number α(G) $\alpha (G)$ and the dissociation number diss(G) $\text{diss}(G)$ of a graph G $G$ are the largest orders of induced subgraphs of G $G$ of maximum degree at most 0 and at most 1, respectively. We consider possible improvements of the obvious inequality 2α(G)≥diss(G) $2\alpha (G)\ge \text{diss}(G)$. For connected cubic graphs G $G$ distinct from K4 ${K}_{4}$, we show 5α(G)≥3diss(G) $5\alpha (G)\ge 3\,\text{diss}(G)$, and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle‐free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs. [ABSTRACT FROM AUTHOR]

Let m $m$ and r $r$ be positive integers with r≥3 $r\ge 3$, let G $G$ be an r $r$‐regular cyclically ((m−1)r+1) $((m-1)r+1)$‐edge‐connected bipartite graph and let M $M$ be a matching of size m $m$ in G $G$. Plummer showed that whenever r≥m+1 $r\ge m+1$, there is a perfect matching of G $G$ containing M $M$. When r=3 $r=3$, Aldred and Jackson, extended this result to the case when m+1≥r=3 $m+1\ge r=3$ by showing there is a perfect matching in G $G$ containing M $M$ whenever the edges in M $M$ are pairwise at least distance f(m) $f(m)$ apart where f(m)=1,m=23,3≤m≤44,5≤m≤85,m≥9. $f(m)=\left\{\begin{array}{ll}1, & m=2\\ 3, & 3\le m\le 4\\ 4, & 5\le m\le 8\\ 5, & m\ge 9.\end{array}\right.$ In this paper, we relax the condition that r=3 $r=3$ and the distance restriction introduced by Aldred and Jackson to show that, for m≥r≥3 $m\ge r\ge 3$ and G $G$ an r $r$‐regular cyclically ((m−1)r+1) $((m-1)r+1)$‐edge‐connected bipartite graph, for each matching M $M$ in G $G$ with ∣M∣=m $| M| =m$ and such that each pair of edges in M $M$ is distance at least 3 apart, there is a perfect matching in G $G$ containing M $M$. [ABSTRACT FROM AUTHOR]

Moon's classical result implies that the number of spanning trees of a complete graph Kn with n vertices containing a given spanning forest F equals nc−2∏i=1cni, where c is the number of components of F, and n1,n2,...,nc are the numbers of vertices of component of F. Dong and Ge extended this result to the complete bipartite graph, and obtain an interesting formula to count spanning trees of a complete bipartite graph Km,n containing a given spanning forest F. They also posed the problem to count spanning trees of a complete s‐partite graph containing a given spanning forest for s≥3. In this paper, we propose a technique to solve this problem. Using this technique, we obtain closed formulae to count spanning trees of complete s‐partite graphs containing a given spanning forest for s=3 and 4. Our technique also results in a new and simple proof of Dong and Ge's formula. [ABSTRACT FROM AUTHOR]

The dissociation number diss(G) $\text{diss}(G)$ of a graph G $G$ is the maximum order of a set of vertices of G $G$ inducing a subgraph that is of maximum degree at most 1. Computing the dissociation number of a given graph is algorithmically hard even when restricted to subcubic bipartite graphs. For a graph G $G$ with n $n$ vertices, m $m$ edges, k $k$ components, and c1 ${c}_{1}$ induced cycles of length 1 modulo 3, we show diss(G)≥n−13(m+k+c1) $\text{diss}(G)\ge n-\frac{1}{3}(m+k+{c}_{1})$. Furthermore, we characterize the extremal graphs in which every two cycles are vertex‐disjoint. [ABSTRACT FROM AUTHOR]

Consider a sequence of Lexicographic Breadth‐First‐Search vertex orderings σ1,σ2,... ${\sigma }_{1},{\sigma }_{2},\ldots $ where each ordering σi ${\sigma }_{i}$ is used to break ties for σi+1 ${\sigma }_{i+1}$. Since the total number of vertex orderings of a finite graph is finite, this sequence must end in a cycle of vertex orderings. The possible length of this cycle is the main subject of this work. Intuitively, we prove for graphs with a known notion of linearity (e.g., interval graphs with their interval representation on the real line), this cycle cannot be too big, no matter which vertex ordering we start with. More precisely, it was conjectured by Dusart and Habib that for cocomparability graphs, the size of this cycle is always 2, independent of the starting order. Furthermore Stacho asked whether for arbitrary graphs, the size of such a cycle is always bounded by the asteroidal number of the graph. In this work, while we answer this latter question negatively, we provide support for the conjecture on cocomparability graphs by proving it for the subclass of domino‐free cocomparability graphs. This subclass contains cographs, proper interval, interval and cobipartite graphs. We also provide simpler independent proofs for each of these cases which lead to stronger results on this subclasses. [ABSTRACT FROM AUTHOR]

Given positive integers p $p$ and q $q$, a (p,q) $(p,q)$‐coloring of the complete graph Kn ${K}_{n}$ is an edge‐coloring in which every p $p$‐clique receives at least q $q$ colors. Erdős and Shelah posed the question of determining f(n,p,q) $f(n,p,q)$, the minimum number of colors needed for a (p,q) $(p,q)$‐coloring of Kn ${K}_{n}$. In this paper, we expand on the color energy technique introduced by Pohoata and Sheffer to prove new lower bounds on this function, making explicit the connection between bounds on extremal numbers and f(n,p,q) $f(n,p,q)$. Using results on the extremal numbers of subdivided complete graphs, theta graphs, and subdivided complete bipartite graphs, we generalize results of Fish, Pohoata, and Sheffer, giving the first nontrivial lower bounds on f(n,p,q) $f(n,p,q)$ for some pairs (p,q) $(p,q)$ and improving previous lower bounds for other pairs. [ABSTRACT FROM AUTHOR]

Let D $D$ be a k $k$‐regular bipartite tournament on n $n$ vertices. We show that, for every p $p$ with 2≤p≤n∕2−2 $2\le p\le n\unicode{x02215}2-2$, D $D$ has a cycle C $C$ of length 2p $2p$ such that D\C $D\backslash C$ is Hamiltonian unless D $D$ is isomorphic to the special digraph F4k ${F}_{4k}$. This statement was conjectured by Zhang, Manoussakis and Song. In the same paper, the conjecture was proved for p=2 $p=2$ and more recently Bai, Li and He gave a proof for p=3 $p=3$. [ABSTRACT FROM AUTHOR]

Let H be a tree. It was proved by Rödl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph Kt,t as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree H , the degeneracy is at most polynomial in t . This answers a question of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak. [ABSTRACT FROM AUTHOR]

Let χ(F2) $\chi ({F}^{2})$ be the Euler characteristic of a surface F2 ${F}^{2}$. We characterize the set of graphs H $H$ of order at most 6 which satisfies the following: If G $G$ is a 5‐connected graph embedded in a surface F2 ${F}^{2}$ of face‐width at least 3∣H∣−2χ(F2)−5 $3| H| -2\chi ({F}^{2})-5$ and H′ $H^{\prime} $ is a subgraph of G $G$ isomorphic to H $H$ such that G−H′ $G-H^{\prime} $ has even order, then G−H′ $G-H^{\prime} $ has a perfect matching. An analogous result on near‐perfect matching is given as well. Moreover, we show the following result. Let G $G$ be a 5‐connected graph embedded in a surface F2 ${F}^{2}$ and let H1,...,Hm ${H}_{1},\ldots ,{H}_{m}$ be connected subgraphs of G $G$ of size at most k $k$ which lie pairwise sufficiently far apart in the face‐subdivision of G $G$. We prove that, if the face‐width of G $G$ is at least max{12(9km−7χ(F2)−20),6} $\max \{\frac{1}{2}(9km-7\chi ({F}^{2})-20),6\}$ and G−Hi $G-{H}_{i}$ satisfies C(1) ${\mathscr{C}}(1)$ for each i $i$ with 1≤i≤m $1\le i\le m$, then G−(H1∪...∪Hm) $G-({H}_{1}\cup \ldots \,\cup {H}_{m})$ satisfies C(1) ${\mathscr{C}}(1)$ as well, where G $G$ is said to satisfy C(1) ${\mathscr{C}}(1)$ if G−S $G-S$ has at most ∣S∣+1 $| S| +1$ components for every S⊆V(G) $S\subseteq V(G)$. It is also shown that the distance condition can be considerably weakened when G $G$ triangulates the surface. All of these results generalize previous studies on matching extension in graphs on surfaces. [ABSTRACT FROM AUTHOR]

Given a graph G $G$, the k $k$‐mixing problem asks: Starting with a k $k$‐colouring of G $G$, can one obtain all k $k$‐colourings of G $G$ by changing the colour of only one vertex at a time, while at each step maintaining a k $k$‐colouring? More generally, for a graph H $H$, the H $H$‐mixing problem asks: Can one obtain all homomorphisms G→H $G\to H$, starting from one homomorphism f $f$, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism G→H $G\to H$? This paper focuses on a generalization of k $k$‐colourings, namely, (p,q) $(p,q)$‐circular colourings. We show that when 2

Let f(n,H) $f(n,H)$ denote the maximum number of copies of H $H$ possible in an n $n$‐vertex planar graph. The function f(n,H) $f(n,H)$ has been determined when H $H$ is a cycle of length 3 or 4 by Hakimi and Schmeichel and when H $H$ is a complete bipartite graph with smaller part of size 1 or 2 by Alon and Caro. We determine f(n,H) $f(n,H)$ exactly in the case when H $H$ is a path of length 3. [ABSTRACT FROM AUTHOR]

For any positive integer k $k$, we show that every maximal C2k+1 ${C}_{2k+1}$‐free graph with at least n2∕4−o(n3∕2) ${n}^{2}\unicode{x02215}4-o({n}^{3\unicode{x02215}2})$ edges contains an induced complete bipartite subgraph on (1−o(1))n $(1-o(1))n$ vertices. We also show that this is the best possible. [ABSTRACT FROM AUTHOR]

In this article, we extend Moon's classic formula for counting spanning trees in complete graphs containing a fixed spanning forest to complete bipartite graphs. Let (X,Y) $(X,Y)$ be the bipartition of the complete bipartite graph Km,n ${K}_{m,n}$ with ∣X∣=m $| X| =m$ and ∣Y∣=n $| Y| =n$. We prove that for any given spanning forest F $F$ of Km,n ${K}_{m,n}$ with components T1,T2,...,Tk ${T}_{1},{T}_{2},\ldots ,{T}_{k}$, the number of spanning trees in Km,n ${K}_{m,n}$ which contain all edges in F $F$ is equal to 1mn∏i=1k(min+nim)1−∑i=1kminimin+nim, $\frac{1}{mn}\left(\prod _{i=1}^{k}({m}_{i}n+{n}_{i}m)\right)\left(1-\sum _{i=1}^{k}\frac{{m}_{i}{n}_{i}}{{m}_{i}n+{n}_{i}m}\right),$ where mi=∣V(Ti)∩X∣ ${m}_{i}=| V({T}_{i})\cap X| $ and ni=∣V(Ti)∩Y∣ ${n}_{i}=| V({T}_{i})\cap Y| $ for i=1,2,...,k $i=1,2,\ldots ,k$. [ABSTRACT FROM AUTHOR]

In this paper we are interested in an intrinsic property of graphs which is derived from their embeddings into the Euclidean 3‐space R3. An embedding of a graph into R3 is said to be linear, if it sends every edge to be a line segment. And we say that an embedding f of a graph G into R3 is free, if π1(R3−f(G)) is a free group. Lastly a simple connected graph is said to be linearly free if every its linear embedding is free. In the 1980s it was proved that every complete graph is linearly free, by Nicholson. In this paper, we develop Nicholson's arguments into a general notion, and establish a sufficient condition for a linear embedding to be free. As an application of the condition we give a partial answer for a question: How much can the complete graph Kn be enlarged so that the linear‐freeness is preserved and the clique number does not increase? And an example supporting our answer is provided. As the second application it is shown that a simple connected graph of minimal valency at least 3 is linearly free, if it has less than eight vertices. The conditional inequality is strict, because we found a graph with eight vertices which are not linearly free. It is also proved that for n,m≤6 the complete bipartite graph Kn,m is linearly free. [ABSTRACT FROM AUTHOR]

Let H be a connected bipartite graph with n vertices and m edges. We give an O(nm) time algorithm to decide whether H is an interval bigraph. The best known algorithm has time complexity O(nm6(m+n)logn) and it was developed by Muller in 1997. Our approach is based on an ordering characterization of interval bigraphs introduced by Hell and Huang in 2003. We transform the problem of finding the desired ordering to choosing strong components of a pair‐digraph without creating conflicts. We make use of the structure of the pair‐digraph as well as decomposition of bigraph H based on the special components of the pair‐digraph. This way we make explicit what the difficult cases are and gain efficiency by isolating such situations. [ABSTRACT FROM AUTHOR]

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. The edge‐biclique graph of G, KBe(G), is the edge‐intersection graph of the bicliques of G. A graph G diverges (resp. converges or is periodic) under an operator H whenever limk→∞∣V(Hk(G))∣=∞ (resp. limk→∞Hk(G)=Hm(G) for some m or Hk(G)=Hk+s(G) for some k and s≥2). The iterated edge‐biclique graph of G, KBek(G), is the graph obtained by applying the edge‐biclique operator k successive times to G. In this article, we first study the connectivity relation between G and KBe(G). Next, we study the iterated edge‐biclique operator KBe. In particular, we give sufficient conditions for a graph to be convergent or divergent under the operator KBe, we characterize the behavior of burgeon graphs and we propose some general conjectures on the subject. [ABSTRACT FROM AUTHOR]

In the language of hypergraphs, our main result is a Dirac‐type bound: We prove that every 3‐connected hypergraph ℋ with δ(H)≥max{∣V(H)∣,∣E(H)∣+ 104} has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite. [ABSTRACT FROM AUTHOR]

Isoradial embeddings of planar graphs play a crucial role in the study of several models of statistical mechanics, such as the Ising and dimer models. Kenyon and Schlenker give a combinatorial characterization of planar graphs admitting an isoradial embedding, and describe the space of such embeddings. In this paper we prove two results of the same type for generalizations of isoradial embeddings: isoradial immersions and minimal immersions. We show that a planar graph admits a flat isoradial immersion if and only if its train‐tracks do not form closed loops, and that a bipartite graph has a minimal immersion if and only if it is minimal. In both cases we describe the space of such immersions. The techniques used are different in both settings, and distinct from those of Kenyon and Schlenker. We also give an application of our results to the dimer model defined on bipartite graphs admitting minimal immersions. [ABSTRACT FROM AUTHOR]

Generalizing well‐known results of Erdős and Lovász, we show that every graph G contains a spanning k‐partite subgraph H with λ(H)≥k−1kλ(G), where λ(G) is the edge‐connectivity of G. In particular, together with a well‐known result due to Nash‐Williams and Tutte, this implies that every 7‐edge‐connected graph contains a spanning bipartite graph whose edge set decomposes into two edge‐disjoint spanning trees. We show that this is best possible as it does not hold for infinitely many 6‐edge‐connected graphs. For directed graphs, it was shown by Bang‐Jensen et al. that there is no k such that every k‐arc‐connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3‐partite subdigraph and that every strong semicomplete digraph on at least six vertices contains a spanning strong bipartite subdigraph. We generalize this result to higher connectivities by proving that, for every positive integer k, every k‐arc‐connected digraph contains a spanning (2k+1)‐partite subdigraph which is k‐arc‐connected and this is best possible. A conjecture by Kreutzer et al. implies that every digraph of minimum out‐degree 2k−1 contains a spanning 3‐partite subdigraph with minimum out‐degree at least k. We prove that the bound 2k−1 would be best possible by providing an infinite class of digraphs with minimum out‐degree 2k−2 which do not contain any spanning 3‐partite subdigraph in which all out‐degrees are at least k. We also prove that every digraph of minimum semidegree at least 3r contains a spanning 6‐partite subdigraph in which every vertex has in‐ and out‐degree at least r. [ABSTRACT FROM AUTHOR]

A graph algorithm is truly subquadratic if it runs in O(mb) time on connected m‐edge graphs, for some positive b<2. Roditty and Vassilevska Williams (STOC'13) proved that under plausible complexity assumptions, there is no truly subquadratic algorithm for computing the diameter of general graphs. In this study, we present positive and negative results on the existence of such algorithms for computing the diameter on some special graph classes. Specifically, three vertices in a graph form an asteroidal triple (AT) if between any two of them there exists a path that avoids the closed neighbourhood of the third one. We call a graph AT‐free if it does not contain an AT. We first prove that for all m‐edge AT‐free graphs, one can compute all the eccentricities in truly subquadratic O(m3∕2) time. For the AT‐free bipartite graphs, it can be improved to linear time. Then, we extend our study to several subclasses of chordal graphs—all of them generalizing interval graphs in various ways—as an attempt to understand which of the properties of AT‐free graphs, or natural generalizations of the latter, can help in the design of fast algorithms for the diameter problem on broader graph classes. For instance, for all chordal graphs with a dominating shortest‐path, there is a linear‐time algorithm for computing a diametral pair if the diameter is at least four. However, already for split graphs with a dominating edge, under plausible complexity assumptions, there is no truly subquadratic algorithm for deciding whether the diameter is either 2 or 3. [ABSTRACT FROM AUTHOR]

A graph is called equimatchable if all of its maximal matchings have the same size. Frendrup et al. provided a characterization of equimatchable graphs with girth at least 5. In this paper, we extend this result by providing a complete structural characterization of equimatchable graphs with girth at least 4, that is, equimatchable graphs with no triangle, by identifying the equimatchable triangle‐free graph families. Our characterization also extends the result given by Akbari et al., which proves that the only connected triangle‐free equimatchable r‐regular graphs are C5, C7, and Kr,r, where r is a positive integer. Given a nonbipartite graph, our characterization implies a linear time recognition algorithm for triangle‐free equimatchable graphs. [ABSTRACT FROM AUTHOR]

Let ϕc(G) be the circular flow number of a bridgeless graph G. By Steffen it was proved that, for a bridgeless (2t+1)‐regular graph G, where t≥1 is a positive integer, ϕc(G)∈{2+1t,2+22t−1} if and only if G has a perfect matching M such that G−M is bipartite. This implies that G is a class 1 graph. For t=1, all graphs with circular flow number bigger than 4 are class 2 graphs. We show that, for all t≥1, 2+22t−1=inf{ϕc(G):G is a (2t+1)‐regular class 2 graph}. This was conjectured to be true by Steffen. Moreover we prove that, for all t≥1, inf{ϕc(G):G is a (2t+1)‐regular class 1 graph with no perfect matching whose removal leaves a bipartite graph=2+22t−1. We further disprove the conjecture that every (2t+1)‐regular class 1 graph has circular flow number at most 2+2t. [ABSTRACT FROM AUTHOR]

An antimagic labeling of a directed graph D with n vertices and m arcs is a bijection from the set of arcs of D to the integers {1,...,m} such that all n oriented vertex sums are pairwise distinct, where an oriented vertex sum is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. A graph has an antimagic orientation if it has an orientation that admits an antimagic labeling. Hefetz, Mütze, and Schwartz conjectured that every connected graph admits an antimagic orientation. In this paper, we show that every bipartite graph with no vertex of degree 0 or 2 admits an antimagic orientation and every graph with minimum degree at least 33 admits an antimagic orientation. [ABSTRACT FROM AUTHOR]

A bisection of a graph is a bipartition of its vertex set in which the two classes differ in size by at most one. For a random bisection of a graph with m edges, one expects m∕4 edges spans in one vertex class. Bollobás and Scott asked for conditions that guarantee a bisection in which both classes span at most (1∕4+o(1))m edges simultaneously. Let δ,ℓ be integers with ℓ≥δ≥2, and let G be a graph with minimum degree δ and m edges. In this article, we prove that if G contains neither triangle nor Kδ,ℓ as a subgraph, then G admits a bisection in which both classes span at most (1∕4+o(1))m edges. We also consider Max‐Bisections of graphs without Kδ,ℓ and improve a recent result of Hou and Yan. [ABSTRACT FROM AUTHOR]

The Turán number of a graph H, ex(n,H), is the maximum number of edges in a graph of order n that does not contain a copy of H as a subgraph. Lidický, Liu and Palmer determined ex(n,Fk1,...,km) for sufficiently large n and proved that the extremal graph is unique, where Fk1,...,km is the union of pairwise vertex‐disjoint paths on k1,...,km vertices. There are a few kinds of graphs F for which ex(n,F) are known exactly for all n, including cliques, matchings, paths, cycles on odd number of vertices and some other special graphs. In this paper, using a different approach from Lidický, Liu and Palmer, we determine ex(n,Fk1,...,km) for all integers n when at most one of k1,...,km is odd. Furthermore, we show that there exists a family of pairs of bipartite graphs (F,G) such that ex(n,F)=ex(n,G) for all integers n, which is related to an old problem of Erdős and Simonovits. [ABSTRACT FROM AUTHOR]

Given a graph G, the strong clique index of G, denoted ωS(G), is the maximum size of a set S of edges such that every pair of edges in S has distance at most 2 in the line graph of G. As a relaxation of the renowned Erdős–Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique index, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if G is a C2k‐free graph with Δ(G)≥max{4,2k−2}, then ωS(G)≤(2k−1)Δ(G)−2k−12, and if G is a C2k‐free bipartite graph, then ωS(G)≤kΔ(G)−(k−1). We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a {C5,C2k}‐free graph G with Δ(G)≥1 satisfies ωS(G)≤kΔ(G)−(k−1), when either k≥4 or k∈{2,3} and G is also C3‐free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for k≥3, we prove that a C2k‐free graph G with Δ(G)≥1 satisfies ωS(G)≤(2k−1)Δ(G)+(2k−1)2. This improves some results of Cames van Batenburg, Kang, and Pirot. [ABSTRACT FROM AUTHOR]

The cyclic matching sequenceability of a simple graph G, denoted cms(G), is the largest integer s for which there exists a cyclic ordering of the edges of G so that every set of s consecutive edges forms a matching. In this paper we consider the minimum cyclic matching sequenceability of k‐regular graphs. We completely determine this for 2‐regular graphs, and give bounds for k⩾3. [ABSTRACT FROM AUTHOR]