The strong chromatic number χs(G) of a graph G on n vertices is the least number r with the following property: after adding $r\lceil n/r\rceil-n$ isolated vertices to G and taking the union with any collection of spanning disjoint copies of Kr in the same vertex set, the resulting graph has a proper vertex colouring with r colours. We show that for every c > 0 and every graph G on n vertices with Δ(G) ≥ cn, χs(G) ≤ (2+o(1))Δ(G), which is asymptotically best possible.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, 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$. Alon et al. [‘Maximum cuts and judicious partitions in graphs without short cycles’, J. Combin. Theory Ser. B 88 (2003), 329–346] conjectured that, for any fixed graph $H$, there exists an $\unicode[STIX]{x1D716}(H)>0$ such that $f(m,H)\geq m/2+\unicode[STIX]{x1D6FA}(m^{3/4+\unicode[STIX]{x1D716}})$. We show that, for any wheel graph $W_{2k}$ of $2k$ spokes, there exists $c(k)>0$ such that $f(m,W_{2k})\geq m/2+c(k)m^{(2k-1)/(3k-1)}\log m$. In particular, we confirm the conjecture asymptotically for $W_{4}$ and give general lower bounds for $W_{2k+1}$.

The paper introduces a graph theory variation of the general position problem: given a graph $G$, determine a largest set $S$ of vertices of $G$ such that no three vertices of $S$ lie on a common geodesic. Such a set is a max-gp-set of $G$ and its size is the gp-number $\text{gp}(G)$ of $G$. Upper bounds on $\text{gp}(G)$ in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.

A perfect H-tiling in a graph G is a collection of vertex-disjoint copies of a graph H in G that together cover all the vertices in G. In this paper we investigate perfect H-tilings in a random graph model introduced by Bohman, Frieze and Martin [6] in which one starts with a dense graph and then adds m random edges to it. Specifically, for any fixed graph H, we determine the number of random edges required to add to an arbitrary graph of linear minimum degree in order to ensure the resulting graph contains a perfect H-tiling with high probability. Our proof utilizes Szemerédi's Regularity Lemma [29] as well as a special case of a result of Komlós [18] concerning almost perfect H-tilings in dense graphs.

We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an n-vertex graph G with sublinear independence number. In this setting, we show that if δ(G) ≥ n/3 + o(n), then G has a triangle-tiling covering all but at most four vertices. Also, for every r ≥ 5, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that G is Kr-free and n is divisible by 3.

It follows from known results that every regular tripartite hypergraph of positive degree, with n vertices in each class, has matching number at least n/2. This bound is best possible, and the extremal configuration is unique. Here we prove a stability version of this statement, establishing that every regular tripartite hypergraph with matching number at most (1 + ϵ)n/2 is close in structure to the extremal configuration, where ‘closeness’ is measured by an explicit function of ϵ.

Let k ⩾ 3 be an integer, hk(G) be the number of vertices of degree at least 2k in a graph G, and ℓk(G) be the number of vertices of degree at most 2k − 2 in G. Dirac and Erdős proved in 1963 that if hk(G) − ℓk(G) ⩾ k2 + 2k − 4, then G contains k vertex-disjoint cycles. For each k ⩾ 2, they also showed an infinite sequence of graphs Gk(n) with hk(Gk(n)) − ℓk(Gk(n)) = 2k − 1 such that Gk(n) does not have k disjoint cycles. Recently, the authors proved that, for k ⩾ 2, a bound of 3k is sufficient to guarantee the existence of k disjoint cycles, and presented for every k a graph G0(k) with hk(G0(k)) − ℓk(G0(k)) = 3k − 1 and no k disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac–Erdős construction is optimal in the sense that for every k ⩾ 2, there are only finitely many graphs G with hk(G) − ℓk(G) ⩾ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ⩾ 19k and hk(G) − ℓk(G) ⩾ 2k contains k disjoint cycles.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. For an integer $m$ and for 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 give a general lower bound for $f(m,H)$ which extends a result of Erdős and Lovász and we study this function for any bipartite graph $H$ with maximum degree at most $t\geq 2$ on one side.

A simple graph $G=(V,E)$ admits an $H$-covering if every edge in $E$ belongs to at least one subgraph of $G$ isomorphic to a given graph $H$. Then the graph $G$ is $(a,d)$-$H$-antimagic if there exists a bijection $f:V\cup E\rightarrow \{1,2,\ldots ,|V|+|E|\}$ such that, for all subgraphs $H^{\prime }$ of $G$ isomorphic to $H$, the $H^{\prime }$-weights, $wt_{f}(H^{\prime })=\sum _{v\in V(H^{\prime })}f(v)+\sum _{e\in E(H^{\prime })}f(e)$, form an arithmetic progression with the initial term $a$ and the common difference $d$. When $f(V)=\{1,2,\ldots ,|V|\}$, then $G$ is said to be super $(a,d)$-$H$-antimagic. In this paper, we study super $(a,d)$-$H$-antimagic labellings of a disjoint union of graphs for $d=|E(H)|-|V(H)|$.

For each of the notions of hypergraph quasirandomness that have been studied, we identify a large class of hypergraphs F so that every quasirandom hypergraph H admits a perfect F-packing. An informal statement of a special case of our general result for 3-uniform hypergraphs is as follows. Fix an integer r ⩾ 4 and 0 < p < 1. Suppose that H is an n-vertex triple system with r|n and the following two properties:

• • for every graph G with V(G) = V(H), at least p proportion of the triangles in G are also edges of H,

• • for every vertex x of H, the link graph of x is a quasirandom graph with density at least p.

For two given graphs $G_{1}$ and $G_{2}$, the Ramsey number $R(G_{1},G_{2})$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G$ contains $G_{1}$ as a subgraph or the complement of $G$ contains $G_{2}$ as a subgraph. A fan $F_{l}$ is $l$ triangles sharing exactly one vertex. In this note, it is shown that $R(F_{n},F_{m})=4n+1$ for $n\geq \max \{m^{2}-m/2,11m/2-4\}$.

For a positive integer r ≥ 2, a Kr-factor of a graph is a collection vertex-disjoint copies of Kr which covers all the vertices of the given graph. The celebrated theorem of Hajnal and Szemerédi asserts that every graph on n vertices with minimum degree at least $(1-\frac{1}{r})n contains a Kr-factor. In this note, we propose investigating the relation between minimum degree and existence of perfect Kr-packing for edge-weighted graphs. The main question we study is the following. Suppose that a positive integer r ≥ 2 and a real t ∈ [0, 1] is given. What is the minimum weighted degree of Kn that guarantees the existence of a Kr-factor such that every factor has total edge weight at least $$t\binom{r}{2}$?$ We provide some lower and upper bounds and make a conjecture on the asymptotics of the threshold as n goes to infinity.

A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt. A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥ (t − 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, …, Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.

Böttcher, Schacht and Taraz (Math. Ann., 2009) gave a condition on the minimum degree of a graph G on n vertices that ensures G contains every r-chromatic graph H on n vertices of bounded degree and of bandwidth o(n), thereby proving a conjecture of Bollobás and Komlós (Combin. Probab. Comput., 1999). We strengthen this result in the case when H is bipartite. Indeed, we give an essentially best-possible condition on the degree sequence of a graph G on n vertices that forces G to contain every bipartite graph H on n vertices of bounded degree and of bandwidth o(n). This also implies an Ore-type result. In fact, we prove a much stronger result where the condition on G is relaxed to a certain robust expansion property. Our result also confirms the bipartite case of a conjecture of Balogh, Kostochka and Treglown concerning the degree sequence of a graph which forces a perfect H-packing.