Let $G=(V(G),E(G))$ be a graph. For a positive integer $k$, we call $S\subseteq V(G)$ a $k$-component independent set of $G$ if each component of $G[S]$ has order at most $k$. Moreover, $S$ is maximal if there does not exist a $k$-component independent set $S^{\prime }$ of $G$ such that $S\subseteq S^{\prime }$ and $|S|<|S^{\prime }|$. A maximal $k$-component independent set of a graph $G$ is denoted briefly by Mk-CIS. We use $t_k(G)$ to denote the number of Mk-CISs of a graph $G$. In this paper, we show that for a forest $G$ of order $n$,

$$t_2(G)\le \{\begin{array}{ll}{3}^{\frac{n}{3}},& \text{if}n\equiv 0(mod3)\text{and}n\ge 3,\\ 4\cdot 3^{\frac{n-4}{3}},& \text{if}n\equiv 1(mod3)\text{and}n\ge 4,\\ 5,& \text{if}n=5,\\ 4^2\cdot 3^{\frac{n-8}{3}},& \text{if}n\equiv 2(mod3)\text{and}n\ge 8,\end{array}$$

with equality if and only if $G\cong F_n$, where

$$F_n\cong \{\begin{array}{ll}\frac{n}{3}{P}_3,& \text{if}n\equiv 0(mod3)\text{and}n\ge 3,\\ \frac{n-4}{3}{P}_3\cup K_{1,3},& \text{if}n\equiv 1(mod3)\text{and}n\ge 4,\\ K_{1,4},& \text{if}n=5,\\ \frac{n-8}{3}{P}_3\cup 2K_{1,3},& \text{if}n\equiv 2(mod3)\text{and}n\ge 8.\end{array}$$

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).