As one of the counting-based topological indices, the number of subtrees and its variations has received much attention in recent years. In this paper, using generating functions, we investigate and derive formulas for this index of hexagonal and phenylene chains. We also present graph-theoretical algorithms for enumerating subtrees of these two chains. Extremal values and graphs with respect to the subtree number among all hexagonal and phenylene chains with n hexagons are also determined. As an application, we briefly examine the subtree densities of these two chains.

A classical result of Hajnal and Szemerédi, when translated to a complementary form, states that with sufficient minimum degree, a graph will contain disjoint large cliques. We conjecture a generalization of this result from cliques to cycles with many chords and prove this conjecture in several cases.

We consider a forbidden rainbow structure condition which implies that an edge colored complete graph has an almost spanning monochromatic subgraph with high connectivity. Namely, we classify the connected graphs $G$ that satisfy the following statement: If $n\,{\gg}\,m\,{\gg}\,k$ are integers, then any rainbow $G$-free coloring of the edges of $K_{n}$ using $m$ colors contains a monochromatic $k$-connected subgraph of order at least $n - f(G, k, m)$, where $f$ does not depend on $n$.