Search

A graph G arrows a graph H if in every 2-edge-colouring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph $K_n$ arrows a small graph H, then every 'dense' subgraph of $K_n$ also arrows H, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large n, if $n = 3t+r$ where $r \in \{0,1,2\}$ and G is an n-vertex graph with $\delta(G) \ge (3n-1)/4$ , then for every 2-edge-colouring of G, either there are cycles of every length $\{3, 4, 5, \dots, 2t+r\}$ of the same colour, or there are cycles of every even length $\{4, 6, 8, \dots, 2t+2\}$ of the samecolour. Our result is tight in the sense that no longer cycles (of length $>2t+r$) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large n, every $(3t-1)$ -vertex graph G with minimum degree larger than $3|V(G)|/4$ arrows the path $P_{2n}$ with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for $n=3t+r$ where $r \in \{0,1,2\}$ and every n-vertex graph G with $\delta(G) \ge 3n/4$ , in each 2-edge-colouring of G there exists a monochromatic cycle of length at least $2t+r$. [ABSTRACT FROM AUTHOR]

Abstract: Let n , d be integers with 1 ≤ d ≤ ⌊ n − 1 2 ⌋, and set h ( n , d ) : = n − d 2 + d 2. Erdős proved that when n ≥ 6 d, each n‐vertex nonhamiltonian graph G with minimum degree δ ( G ) ≥ d has at most h ( n , d ) edges. He also provides a sharpness example H n , d for all such pairs n , d. Previously, we showed a stability version of this result: for n large enough, every nonhamiltonian graph G on n vertices with δ ( G ) ≥ d and more than h ( n , d + 1 ) edges is a subgraph of H n , d. In this article, we show that not only does the graph H n , d maximize the number of edges among nonhamiltonian graphs with n vertices and minimum degree at least d, but in fact it maximizes the number of copies of any fixed graph F when n is sufficiently large in comparison with d and | F |. We also show a stronger stability theorem, that is, we classify all nonhamiltonian n‐vertex graphs with δ ( G ) ≥ d and more than h ( n , d + 2 ) edges. We show this by proving a more general theorem: we describe all such graphs with more than n − ( d + 2 ) k + ( d + 2 ) d + 2 k − 1 copies of K k for any k. [ABSTRACT FROM AUTHOR]

A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k-1)-colorable. Let fk(n) denote the minimum number of edges in an n-vertex k-critical graph. Recently the authors gave a lower bound, fk(n)≥⌈(k+1)(k−2)|V(G)|−k[k−3]2(k−1)⌉, that solves a conjecture by Gallai from 1963 and is sharp for every n≡1 (mod k-1). It is also sharp for k=4 and every n≤6. In this paper we refine the result by describing all n-vertex k-critical graphs G with |E(G)|≥(k+1)(k−2)|V(G)|−k(k−3)2(k−1). In particular, this result implies exact values of f5(n) for n≤7. [ABSTRACT FROM AUTHOR]

In 1963, Corradi and Hajnal proved that for all k≥1 and n≥3 k, every (simple) graph G on n vertices with minimum degree δ( G)≥2 k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2 k-1)-connected multigraphs do not contain k disjoint cycles? Recently, the authors characterized the simple graphs G with minimum degree δ( G)≥2 k-1 that do not contain k disjoint cycles. We use this result to answer Dirac's question in full. [ABSTRACT FROM AUTHOR]