Suppose \(\{P_r\}\) is a nonempty family of paths for \(r \geq 3\), where \(P_r\) is a path on \(r\) vertices. An \(r\)-coloring of a graph \(G\) is said to be \(\{P_r\}\)-free if \(G\) contains no 2-colored subgraph isomorphic to any path \(P_r\) in \(\{P_r\}\). The minimum \(k\) such that \(G\) has a \(\{P_r\}\)-free coloring using \(k\) colors is called the \(\{P_r\}\)-free chromatic number of \(G\) and is denoted by \(\chi_{\{P_r\}}(G)\). If the family \(\{P_r\}\) consists of a single graph \(P_r\), then we use \(\chi_{P_r}(G)\). In this paper, \(\{P_r\}\)-free colorings of Sierpiński-like graphs are considered. In particular, \(\chi_{P_3}(S_n)\), \(\chi_{P_4}(S_n)\), \(\chi_{P_4}(S(n, k))\), \(\chi_{P_3}(S^{++}(n, k))\), and \(\chi_{P_4}(S^{++}(n, k))\) are determined.

Let \(G = (V,E)\) be a graph with \(v = |V(G)|\) vertices and \(e = |E(G)|\) edges. An \((a, d)\)-edge-antimagic total labeling of the graph \(G\) is a one-to-one map \(A\) from \(V(G) \cup E(G)\) onto the integers \(\{1,2,\ldots,v+e\}\) such that the set of edge weights of the graph \(G\), \(W = \{w(xy) : xy \in E(G)\}\) form an arithmetic progression with the initial term \(a\) and common difference \(d\), where \(w(xy) =\lambda(x) + \lambda(y) + \lambda(xy)\) for any \(xy \in E(G)\). If \(\lambda(V(G)) = \{1,2,\ldots,v\}\) then \(G\) is super \((a, d)\)-edge-antimagic total, i.e., \((a,d)\)-EAT. In this paper, for different values of \(d\), we formulate super \((a, d)\)-edge-antimagic total labeling on subdivision of stars \(K_{1,p}\) for \(p \geq 5\).

We discuss the chromaticity of one family of \(K_4\)-homeomorphs which has girth \(7\) and has exactly \(1\) path of length \(1\), and give a sufficient and necessary condition for the graphs in the family to be chromatically unique.

A theta graph is denoted by \(\theta(a,b,c)\), where \(a \leq b \leq c\). It is obtained by subdividing the edges of the multigraph consisting of \(3\) parallel edges \(a\) times, \(b\) times, and \(c\) times each. In this paper, we show that the theta graph is matching unique when \(a \geq 2\) or \(a = 0\), and all theta graphs are matching equivalent when only one of the edges is subdivided one time. We also completely characterize the relation between the largest matching root \(\alpha\) and the length of path \(a, b, c\) of a theta graph, and determine the extremal theta graphs.

The line graph of \(G\), denoted \(L(G)\), is the graph with vertex set \(E(G)\), where vertices \(x\) and \(y\) are adjacent in \(L(G)\) if and only if edges \(x\) and \(y\) share a common vertex in \(G\). In this paper, we determine all graphs \(G\) for which \(L(G)\) is a circulant graph. We will prove that if \(L(G)\) is a circulant, then \(G\) must be one of three graphs: the complete graph \(K_4\), the cycle \(C_n\), or the complete bipartite graph \(K_{a,b}\), for some \(a\) and \(b\) with \(\gcd(a,b) = 1\).

Let \(G\) be a graph. The point arboricity of \(G\), denoted by \(\rho (G)\), is the minimum number of colors that can be used to color the vertices of \(G\) so that each color class induces an acyclic subgraph of \(G\). The list point arboricity \(\rho_l(G)\) is the minimum \(k\) so that there is an acyclic \(L\)-coloring for any list assignment \(L\) of \(G\) which \(|L(v)| \geq k\). So \(\rho(G) \leq \rho_l(G)\). Zhen and Wu conjectured that if \(|V(G)| \leq 3\rho (G)\), then \(\rho_l(G) = p(G)\). Motivated by this, we investigate the list point arboricity of some complete multi-partite graphs of order slightly larger than \(3p(G)\), and obtain \(\rho(K_{m,(1),2(n-1)}) = \rho_l(K_{m(1),2(n-1)})\) \((m = 2,3,4)\).

In this paper, we consider the relationship between toughness and the existence of \([a, b]\)-factors. We obtain that a graph \(G\) has an \([a, b]\)-factor if \(t(G) \geq {a-1} + \frac{a-1}{b}\) with \(b > a > 1\). Furthermore, it is shown that the result is best possible in some sense.

The clique graph of a graph \(G\) is the graph whose vertex set is the set of cliques of \(G\) and two vertices are adjacent if and only if the corresponding cliques have non-empty intersection. A graph is self-clique if it is isomorphic to its clique graph. In this paper, we present several results on connected self-clique graphs in which each clique has the same size \(k\) for \(k = 2\) and \(k = 3\).

All parabolic ovals in affine planes of even order \(q \leq 64\) which are preserved by a collineation group isomorphic to \(\mathrm{A\Gamma L}(1,q)\) are determined. They are either parabolas or translation ovals.

We consider the class \({ER}(n, d, \lambda)\) of edge-regular graphs for some \(n > d > \lambda\), i.e., graphs regular of degree \(d\) on \(n\) vertices, with each pair of adjacent vertices having \(\lambda\) common neighbors. It has previously been shown that for such graphs with \(\lambda > 0\) we have \(n \geq 3(d – \lambda)\) and much has been done to characterize such graphs when equality holds.

Here we show that \(n \geq 3(d – \lambda) + 1\) if \(\lambda > 0\) and \(d\) is odd and contribute to the characterization of the graphs in \({ER}(n, d, \lambda)\), \(\lambda > 0\), \(n = 3(d-\lambda)+1\) by proving some lemmas about the structure of such graphs, and by classifying such graphs that satisfy a strong additional requirement, that the number \(t = t(u,v)\) of edges in the subgraph induced by the \(\lambda\) common neighbors of any two adjacent vertices \(u\) and \(v\) is positive, and independent of \(u\) and \(v\). The result is that there are exactly 4 such graphs: \(K_4\) and 3 strongly regular graphs.