Abstract. Let [Formula: see text] denote the maximum number of edges not contained in any monochromatic copy of [Formula: see text] in a [Formula: see text]-coloring of the edges of [Formula: see text], and let [Formula: see text] denote the Turán number of [Formula: see text]. In place of [Formula: see text] we simply write [Formula: see text]. Keevash and Sudakov proved that [Formula: see text] if [Formula: see text] is an edge-critical graph or [Formula: see text] and asked if this equality holds for any graph [Formula: see text]. All known exact values of this question require [Formula: see text] to contain at least one cycle. In this paper we focus on acyclic graphs and present the following results: (1) We prove [Formula: see text] when [Formula: see text] is a spider or a double broom. (2) We show that a tail in [Formula: see text] is a path [Formula: see text] such that [Formula: see text] is only adjacent to [Formula: see text], and [Formula: see text] is only adjacent to [Formula: see text] in [Formula: see text]. We obtain a tight upper bound for [Formula: see text] when [Formula: see text] is a bipartite graph with a tail. This result provides the first bipartite graphs which answer the question of Keevash and Sudakov in the negative. (3) We answer a question of Liu, Pikhurko, and Sharifzadeh who asked if [Formula: see text] when [Formula: see text] is a tree. We provide an upper bound for [Formula: see text] and show it is tight when [Formula: see text] is prime. This provides a negative answer to their question.

Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well-studied function, the planar Turán number of $H$, denoted by ${\rm ex}_{\mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden [ J. Graph Theory, 83 (2016), pp. 213--230]. He obtained a sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Lan, Shi, and Song continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$, which improves Lan, Shi, and Song's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$.

The Wiener index of a graph G, denoted W(G), is the sum of the distances between all non-ordered pairs of vertices in G.É. Czabarka, et al. conjectured that for a simple quadrangulation graph G on n vertices, n≥4, W(G)≤112n3+76n−2,n≡0(mod2), 112n3+1112n−1,n≡1(mod2).In this paper, we confirm this conjecture.

An adjacent vertex distinguishing edge‐coloring of a simple graph G is a proper edge‐coloring of G such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors $\chi^\prime_a(G)$ required to give G an adjacent vertex distinguishing coloring is studied for graphs with no isolated edge. We prove $\chi^\prime_a(G)\le5$ for such graphs with maximum degree $\Delta(G)=3$ and prove $\chi^\prime_a(G)\le\Delta(G)+2$ for bipartite graphs. These bounds are tight. For k‐chromatic graphs G without isolated edges we prove a weaker result of the form $\chi^\prime_a(G)=\Delta(G)+O(\log k)$.

The problem of estimating the number of 1’s in a square 0-1 matrix with certain forbidden configurations is considered, and nearly tight bounds are provided. This is motivated by a problem in computational geometry.