In 1967, Erdős and Hajnal asked the question: Does there exist a \( K_4 \)-free graph that is not the union of two triangle-free graphs? Finding such a graph involves solving a special case of the classical Ramsey arrowing operation. Folkman proved the existence of these graphs in 1970, and they are now called Folkman graphs. Erdős offered \$100 for deciding if one exists with less than \( 10^{10} \) vertices. This problem remained open until 1988 when Spencer, in a seminal paper using probabilistic techniques, proved the existence of a Folkman graph of order \( 3 \times 10^9 \) (after an erratum), without explicitly constructing it. In 2008, Dudek and Rödl developed a strategy to construct new Folkman graphs by approximating the maximum cut of a related graph, and used it to improve the upper bound to 941. We improve this bound first to 860 using their approximation technique and then further to 786 with the MAX-CUT semidefinite programming relaxation as used in the Goemans-Williamson algorithm.

Let a set \([n] = \{1,2,\ldots,n\}\) be given. Finding a subset \( S \) of \( 2^{[n]} \) with minimum cardinality such that, for any two distinct elements \( x, y \in [n] \), there exist disjoint subsets \( A_x, A_y \in \mathcal{S} \) such that \( x \in A_x \) and \( y \in A_y \) is called the \emph{extremal set} problem. In this paper, we define the Extremal Set Decision (ESD) Problem and study its complexity.

A cyclic base ordering of a connected graph \( G \) is a cyclic ordering of \( E(G) \) such that every \( |V(G)| – 1 \) cyclically consecutive edges form a spanning tree of \( G \). Let \( G \) be a graph with \( E(G) \neq \emptyset \) and let \( \omega(G) \) denote the number of components in \( G \). The invariants \( d(G) \) and \( \gamma(G) \) are respectively defined as \( d(G) = \frac{|E(G)|}{|V(G)| – \omega(G)} \) and \( \gamma(G) = \text{max}\{d(H)\} \), where \( H \) runs over all subgraphs of \( G \) with \( E(H) \neq \emptyset \). A graph \( G \) is uniformly dense if \( d(G) = \gamma(G) \). Kajitani et al. [8] conjectured in 1988 that a connected graph \( G \) has a cyclic base ordering if and only if \( G \) is uniformly dense. In this paper, we show that this conjecture holds for some classes of uniformly dense graphs.

A graph \( G \) is a \((t, r)\)-regular graph if every collection of \( t \) independent vertices is collectively adjacent to exactly \( r \) vertices. Let \( p, s \), and \( m \) be positive integers, where \( m \geq 2 \), and let \( G \) be a \((2, r)\)-regular graph. If \( n \) is sufficiently large, then \( G \) is isomorphic to \( K_s + mK_p \), where \( 2(p-1) + s = r \). A nested \((2, r)\)-regular graph is constructed by replacing selected cliques in a \((2, r)\)-regular graph with a \((2, r’)\)-regular graph and joining the vertices of the peripheral cliques. We examine the network properties such as the average path length, clustering coefficient, and the spectrum of these nested graphs.

Given a graph \( G \), we show how to compute the number of (perfect) matchings in the graphs \( G \Box P_n \) and \( G \Box C_n \), by looking at appropriate entries in a power of a particular matrix. We give some generalizations and extensions of this result, including showing how to compute tilings of \( k \times n \) boards using monomers, dimers, and \( 2 \times 2 \) tiles.

Consider a simple undirected graph \( G = (V, E) \). A family of subtrees, \(\{T_v\}_{v \in V}\), of a tree \(\mathcal{T}\) is called a \((\mathcal{T}; t)\)-representation of \(G\) provided \( uv \in E \) if and only if \( |T_u \cap T_v| \geq t \). In this paper, we consider \((\mathcal{T}; t)\)-representations for graphs containing large asteroidal sets, where \(\mathcal{T}\) is a subdivision of the \(n\)-star \(K_{1, n}\). An asteroidal set in a graph \(G\) is a subset \(A\) of the vertex set such that for all 3-element subsets of \(A\), there exists a path in \(G\) between any two of these vertices which avoids the neighborhood of the third vertex. We construct a representation of an asteroidal set of size \( n + \sum_{k=2}^{n} \binom{n}{k} \binom{t-2}{k-1} \) and show that no graph containing a larger asteroidal set can be represented.