Let $G$ be a graph of order $n$. A path decomposition $\mathcal{P}$ of $G$ is a collection of edge-disjoint paths that covers all the edges of $G$. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of $G$. Gallai conjectured that if $G$ is connected, then $p(G)\le \lceil \frac{n}{2}\rceil$. In this paper, we prove that the above conjecture holds for all block graphs.

A proper vertex coloring φ of a graph G is said to be odd if for each non-isolated vertex x ∈ V(G) there exists a color c such that |φ−1(c)∩N_G(x)| is odd. A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove every 1-planar graph admits an odd 21-coloring. This improves a recently obtained bound, 23, due to Cranston, Lafferty and Song.

A subset D ⊆ V (G) is called an $\mathcal{F}$-isolating set of a graph G if G−N[D] contains no subgraph isomorphic to any F ∈ $\mathcal{F}$, where $\mathcal{F}$ is a family of connected graphs. The $\mathcal{F}$-isolation number of G, denoted by ι(G, $\mathcal{F}$), is the minimum cardinality of an $\mathcal{F}$-isolating set in G. In this paper, take $\mathcal{F}$ = {C₃,K_1,3,P₄} and denote ι(G, $\mathcal{F}$) simply by ${{\iota }^{\prime }}_c$,(G) which implies that ${{\iota }^{\prime }}_c$(G) is the order of a smallest set D such that G−N[D] consists of some K₁, K₂ and P₃ only. We prove that if G is a connected graph of order n and different from C₃ or C₇, then ${{\iota }^{\prime }}_c$(G)≤ $\frac{n}{4}$.

Let f(r,n) be the maximum integer k such that every r-edge-colored complete graph K_n contains a monochromatic cycle of length at least k. In 2009, Faudree, Lesniak and Schiermeyer conjectured that every (r+1)-edge-colored complete graph K_n contains a monochromatic cycle of length at least $\frac{n}{r}$ for r ≥ 2. Meanwhile, they also proved that f(2,n) ≥ $\lceil \frac{2n}{3}\rceil$ for n ≥ 6, and this bound is sharp. In 2011, Fujita disproved this conjecture for n=2r and also showed that every r-edge-colored complete graph K_n contains a monochromatic cycle of length at least $\frac{n}{r}$ for 1 ≤ r ≤ n. In this paper, we disprove this conjecture for n=rt+1, where r ≥ 2 and $\frac{n-1}{r}$ is a positive even integer. More precisely, there exists a (r+1)-edge-colored complete graph K_n contains a monochromatic cycle of length less than $\frac{n}{r}$. For a k-edge coloring c of K_n, let moc(K_n,c) be the largest order of monochromatic tree of K_n under c. Let moc(n,k) = min{moc(K_n,c): c is a k-edge coloring of K_n}. We show that for any positive integer n ≥ 3, moc(n,3) = $\lceil \frac{n}{2}\rceil$ if n ≡ 0,1 (mod 4) and moc(n, 3) = $\lceil \frac{n+1}{2}\rceil$ if n ≡ 2,3 (mod 4).