Search

We study the following question: How few edges can we delete from any H $H$‐free graph on n $n$ vertices to make the resulting graph k $k$‐colorable? It turns out that various classical problems in extremal graph theory are special cases of this question. For H $H$ any fixed odd cycle, we determine the answer up to a constant factor when n $n$ is sufficiently large. We also prove an upper bound when H $H$ is a fixed clique that we conjecture is tight up to a constant factor, and prove upper bounds for more general families of graphs. We apply our results to get a new bound on the maximum cut of graphs with a forbidden odd cycle in terms of the number of edges. [ABSTRACT FROM AUTHOR]

Finding the maximum number of induced cycles of length k in a graph on n vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and Pfender answered the question in the case k=5. In this paper we determine precisely, for all sufficiently large n, the maximum number of induced 5‐cycles that an n‐vertex planar graph can contain. [ABSTRACT FROM AUTHOR]

Abstract: We improve the upper bound on the Ramsey number R(5, 5) from R ( 5 , 5 ) ≤ 49 to R ( 5 , 5 ) ≤ 48. We also complete the catalog of extremal graphs for R(4, 5). [ABSTRACT FROM AUTHOR]

We show that a tree of order n has at most [ABSTRACT FROM AUTHOR]

We prove that for every fixed k, the number of occurrences of the transitive tournament Tr k of order k in a tournament [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

We study the topic of 'extremal' planar graphs, defining [ABSTRACT FROM AUTHOR]

A graph is K2, 3 -saturated if it has no subgraph isomorphic to K2, 3, but does contain a K2, 3 after the addition of any new edge. We prove that the minimum number of edges in a K2, 3-saturated graph on [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

A proper edge coloring of a graph G without isolated edges is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor-distinguishing index of G is the minimum number ndi( G) of colors in a neighbor-distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that [ABSTRACT FROM AUTHOR]

It is shown that any graph with maximum degree Δ in which the average degree of the induced subgraph on the set of all neighbors of each vertex exceeds [ABSTRACT FROM AUTHOR]

Extremal problems for graph homomorphisms have recently become a topic of much research. Let [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

We study the degree-diameter problem for claw-free graphs and 2-regular hypergraphs. Let [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]