Two quasigroup identities of importance in combinatorics, Schröder’s Second Law and Stein’s Third Law, share many common features that are incorporated under the guise of palindromic quasigroups. A graph-theoretical technique yields a topological proof for the congruence restrictions on the spectrum of Schröder or outer palindromic quasigroups. The potential for a comparable proof applicable to Stein or inner palindromic quasigroups raises open graph-theoretical and combinatorial problems. Imposition of extra Sudoku-like conditions on Latin squares of square order, based on the coloring of so-called Sudoku graphs, leads to the concept of a Sudoku quasigroup. It is shown that the spectrum of inner palindromic Sudoku quasigroups comprises every perfect square, thereby identifying the chromatic number of each Sudoku graph.

Hoffman proved that for a simple graph \( G \), the chromatic number \( \chi(G) \) obeys \( \chi(G) \geq 1 – \frac{\lambda_1}{\lambda_n} \), where \( \lambda_1 \) and \( \lambda_n \) are the maximal and minimal eigenvalues of the adjacency matrix of \( G \), respectively. Lovász later showed that \( \chi(G) \geq 1 – \frac{\lambda_1}{\lambda_n} \) for any (perhaps negatively) weighted adjacency matrix.

In this paper, we give a probabilistic proof of Lovász’s theorem, then extend the technique to derive generalizations of Hoffman’s theorem when allowed a certain proportion of edge-conflicts. Using this result, we show that if a \( 3 \)-uniform hypergraph is \( 2 \)-colorable, then \( \bar{d} \leq – \frac{3}{2} \lambda_{\text{min}} \) where \( \bar{d} \) is the average degree and \( \lambda_{\text{min}} \) is the minimal eigenvalue of the underlying graph. We generalize this further for \( k \)-uniform hypergraphs, for the cases \( k = 4 \) and \( 5 \), by considering several variants of the underlying graph.

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.