We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation $\mathbb {E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

For a graph $H$ and a hypercube $Q_n$, $\textrm{ex}(Q_n, H)$ is the largest number of edges in an $H$-free subgraph of $Q_n$. If $\lim _{n \rightarrow \infty } \textrm{ex}(Q_n, H)/|E(Q_n)| \gt 0$, $H$ is said to have a positive Turán density in a hypercube or simply a positive Turán density; otherwise, it has zero Turán density. Determining $\textrm{ex}(Q_n, H)$ and even identifying whether $H$ has a positive or zero Turán density remains a widely open question for general $H$. By relating extremal numbers in a hypercube and certain corresponding hypergraphs, Conlon found a large class of graphs, ones having so-called partite representation, that have zero Turán density. He asked whether this gives a characterisation, that is, whether a graph has zero Turán density if and only if it has partite representation. Here, we show that, as suspected by Conlon, this is not the case. We give an example of a class of graphs which have no partite representation, but on the other hand, have zero Turán density. In addition, we show that any graph whose every block has partite representation has zero Turán density in a hypercube.

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$, for every graph $G \in \mathcal{G}$ there is a graph $H$ with $\textrm{tw}(H) \leqslant c$ such that $G$ is isomorphic to a subgraph of $H \boxtimes K_{f(\textrm{tw}(G))}$. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth $3$; the class of $K_{s,t}$-minor-free graphs has underlying treewidth $s$ (for $t \geqslant \max \{s,3\}$); and the class of $K_t$-minor-free graphs has underlying treewidth $t-2$. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.

We first establish a lower bound on the size and spectral radius of a graph G to guarantee that G contains a fractional perfect matching. Then, we determine an upper bound on the distance spectral radius of a graph G to ensure that G has a fractional perfect matching. Furthermore, we construct some extremal graphs to show all the bounds are best possible.

For a graph G, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of G. Given a positive integer m and a fixed graph H, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as G ranges over all graphs on m edges that contain no copy of H. We prove bounds on $f(m,H)$ for some bipartite graphs H and give a bound for a conjecture of Alon et al. [‘MaxCut in H-free graphs’, Combin. Probab. Comput. 14 (2005), 629–647] concerning $f(m,K_{4,s})$.

We consider finite simple graphs. Given a graph H and a positive integer $n,$ the Turán number of H for the order $n,$ denoted $\mathrm {ex}(n,H),$ is the maximum size of a graph of order n not containing H as a subgraph. Erdős asked: ‘For which graphs H is it true that every graph on n vertices and $\mathrm {ex}(n,H)+1$ edges contains at least two H’s? Perhaps this is always true.’ We solve this problem in the negative by proving that for every integer $k\ge 4$ there exists a graph H of order k and at least two orders n such that there exists a graph of order n and size $\mathrm {ex}(n,H)+1$ which contains exactly one copy of $H.$ Denote by $C_4$ the $4$ -cycle. We also prove that for every integer n with $6\le n\le 11$ there exists a graph of order n and size $\mathrm {ex}(n,C_4)+1$ which contains exactly one copy of $C_4,$ but, for $n=12$ or $n=13,$ the minimum number of copies of $C_4$ in a graph of order n and size $\mathrm {ex}(n,C_4)+1$ is two.

We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function L = L(r,ɛ) such that every Kr-free graph G on n vertices with minimum degree at least ((2r–5)/(2r–3)+ɛ)n is homomorphic to a Kr-free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result.

For r = 3 this result was obtained by Łuczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemerédi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L(3, ɛ). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L(r, ɛ) that is doubly exponential in poly(ɛ).

We introduce and study a new model that we call the matching model. Items arrive one by one in a buffer and depart from it as soon as possible but by pairs. The items of a departing pair are said to be matched. There is a finite set of classes 𝒱 for the items, and the allowed matchings depend on the classes, according to a matching graph on 𝒱. Upon arrival, an item may find several possible matches in the buffer. This indeterminacy is resolved by a matching policy. When the sequence of classes of the arriving items is independent and identically distributed, the sequence of buffer-content is a Markov chain, whose stability is investigated. In particular, we prove that the model may be stable if and only if the matching graph is nonbipartite.

In this paper, we investigate the domination, total domination, and semi-total domination numbers of a zero-divisor graph of a commutative Noetherian ring. Also, some relations between the domination numbers of $\Gamma \left( {R}/{I}\; \right)$ and ${{\Gamma }_{1}}\left( R \right)$, and the domination numbers of $\Gamma \left( R \right)$ and $\Gamma \left( R\left[ x,\,\alpha ,\,\delta \right] \right)$, where $R\left[ x,\,\alpha ,\,\delta \right]$ is the Ore extension of $R$, are studied.

Let R = k[x1,…,xn], where k is a field. The path ideal (of length t ≥ 2) of a directed graph G is the monomial ideal, denoted by It(G), whose generators correspond to the directed paths of length t in G. Let Cn be an n-cycle. We show that R/It(Cn) is Sr if and only if it is Cohen-Macaulay or $\lceil \frac{n}{n-t-1}\rceil\geq r+3$. In addition, we prove that R/It(Cn) is Gorenstein if and only if n = t or 2t + 1. Also, we determine all ordinary and symbolic powers of It(Cn) which are Cohen-Macaulay. Finally, we prove that It(Cn) has a linear resolution if and only if t ≥ n − 2.

Let $\mathcal{H}$ be a set of connected graphs. A graph G is said to be $\mathcal{H}$-free if G does not contain any element of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{F}_{k}(\mathcal{H})$ be the set of k-connected $\mathcal{H}$-free graphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow a finite exceptional set of graphs. But if the symmetric difference of $\mathcal{F}_{k}(\mathcal{H}_{1})$ and $\mathcal{F}_{k}(\mathcal{H}_{2})$ is finite and we allow a finite number of exceptions, no graph property can distinguish them. Motivated by this observation, we study when we obtain a finite symmetric difference. In this paper, our main aim is the following. If $|\mathcal{H}|\leq 3$ and the symmetric difference of $\mathcal{F}_{1}(\{H\})$ and $\mathcal{F}_{1}(\mathcal{H})$ is finite, then either $H\in \mathcal{H}$ or $|\mathcal{H}|=3$ and H=C3. Furthermore, we prove that if the symmetric difference of $\mathcal{F}_{k}(\{H_{1}\})$ and $\mathcal{F}_{k}(\{H_{2}\})$ is finite, then H1=H2.

We consider a class of graphs G such that the height of the edge ideal I(G) is half of the number #V(G) of the vertices. We give Cohen-Macaulay criteria for such graphs.

Let $X$ be a locally finite, connected graph without vertices of degree 1. Non-backtracking random walk moves at each step with equal probability to one of the “forward” neighbours of the actual state, i.e., it does not go back along the preceding edge to the preceding state. This is not a Markov chain, but can be turned into a Markov chain whose state space is the set of oriented edges of $X$. Thus we obtain for infinite $X$ that the $n$-step non-backtracking transition probabilities tend to zero, and we can also compute their limit when $X$ is finite. This provides a short proof of an old result concerning cogrowth of groups, and makes the extension of that result to arbitrary regular graphs rigorous. Even when $X$ is non-regular, but small cycles are dense in$X$, we show that the graph $X$ is non-amenable if and only if the non-backtracking $n$-step transition probabilities decay exponentially fast. This is a partial generalization of the cogrowth criterion for regular graphs which comprises the original cogrowth criterion for finitely generated groups of Grigorchuk and Cohen.

Let G be a split graph with the independent part IG and the complete part KG. Suppose that the Dilworth number of (IG, ≼) with respect to the vicinal preorder ≼ is two and that of (KG, ≼) is an integer k. We show that G has a specified graph Hk, defined in this paper, as an induced subgraph.