For a graph \( G \) having chromatic number \( k \), an equivalence relation is defined on the set \( X \) consisting of all proper vertex \( k \)-colorings of \( G \). This leads naturally to an equivalence relation on the set \( \mathcal{P} \) consisting of all partitions of \( V(G) \) into \( k \) independent subsets of color classes. The notion of a partition type arises and the algebra of types is investigated.

We derive a new upper bound of \( 26 \) for the Ramsey number \( R(K_5 – P_3, K_5) \), lowering the previous upper bound of \( 28 \). This leaves \( 25 \leq R(K_5 – P_5, K_5) \leq 26 \), improving on one of the three remaining open cases in Hendry’s table, which listed Ramsey numbers for pairs of graphs \( (G, H) \) with \( G \) and \( H \) having five vertices.

We also show, with the help of a computer, that \( R(B_2, B_6) = 17 \) and \( R(B_2, B_7) = 18 \) by full enumeration of \( (B_2, B_6) \)-\({good}\) graphs and \( (B_2, B_7) \)-\({good}\) graphs, where \( B_n \) is the book graph with \( n \) triangular pages.

Let \( G \) be a simple graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( \mathbb{Z}_2 = \{0,1\} \). Any edge labeling \( f \) induces a partial vertex labeling \( f^+ : V(G) \to \mathbb{Z}_2 \) assigning \( 0 \) or \( 1 \) to \( f^+(v) \), \( v \) being an element of \( V(G) \), depending on whether there are more \( 0 \)-edges or \( 1 \)-edges incident with \( v \), and no label is given to \( f^+(v) \) otherwise. For each \( i \in \mathbb{Z}_2 \), let \( v_f(i) = \lvert \{v \in V(G) : f^+(v) = i\} \rvert \) and let \( e_f(i) = \lvert \{e \in E(G) : f(e) = i\} \rvert \). An edge-labeling \( f \) of \( G \) is said to be edge-friendly if \( \lvert e_f(0) – e_f(1) \rvert \leq 1 \). The edge-balance index set of the graph \( G \) is defined as \( \text{EBI}(G) = \{\lvert v_f(0) – v_f(1) \rvert : f \text{ is edge-friendly}\} \). In this paper, we investigate and present results concerning the edge-balance index sets of \( L \)-products of cycles with stars.

In [A.G. Chetwynd and A.J.W. Hilton, Critical star multigraphs, Graphs and Combinatorics 2(1986), 209-221], Chetwynd and Hilton started the investigations of the edge-chromatic properties of a particular class of multigraphs, which they called star multigraphs. A star multigraph is a multigraph such that there exists a vertex \( v^* \) that is incident with each multiple edge. Star multigraphs turn out to be useful tools in the study of the chromatic index of simple graphs.

The main goal of this paper is to provide shorter and simpler proofs of all the main theorems contained in the above-mentioned paper. Most simplifications are achieved by means of a formula for the chromatic index recently obtained by the author and by a careful use of arguments involving fans.

The existence of an equivalence subset of rational functions with Fibonacci numbers as coefficients and the Golden Ratio as fixed point is proven. The proof is based on two theorems establishing basic relationships underlying the Fibonacci Sequence, Pascal’s Triangle, and the Golden Ratio.

The degree set \( \mathcal{D}(G) \) of a graph \( G \) is the set of degrees of its vertices. It has been shown that when the cardinality of \( \mathcal{D}(G) \) is \( 1 \) (i.e., \( G \) is regular) or \( 2 \) (i.e., \( G \) is bi-regular), the balance index set of \( G \) has simple structures. In this work, we determine the balance index sets of unicyclic graphs and subclasses of \( (p, p+1) \) graphs to demonstrate the application of this recent result. In addition, we give an explicit formula for the balance index sets of subclasses of complete tri-bipartite graphs \( G \) (\(|\mathcal{D}(G)| = 3\)). Structural properties regarding the balance index sets of a general graph \( G \) and application examples are also presented.

Let \( G \) be a simple graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( \mathbb{Z}_2 = \{0,1\} \). Any edge labeling \( f \) induces a partial vertex labeling \( f^+ : V(G) \to \mathbb{Z}_2 \) assigning \( 0 \) or \( 1 \) to \( f^+(v) \), \( v \) being an element of \( V(G) \), depending on whether there are more \( 0 \)-edges or \( 1 \)-edges incident with \( v \), and no label is given to \( f^+(v) \) otherwise. For each \( i \in \mathbb{Z}_2 \), let \( v_f(i) = |\{v \in V(G) : f^+(v) = i\}| \) and \( e_f(i) = |\{e \in E(G) : f(e) = i\}| \). An edge-labeling \( f \) of \( G \) is said to be edge-friendly if \( |e_f(0) – e_f(1)| \leq 1 \). The edge-balance index set of the graph \( G \) is defined as \( \text{EBI}(G) = \{\lvert v_f(0) – v_f(1) \rvert : f \text{ is edge-friendly}\} \). In this paper, we investigate and present results concerning the edge-balance index sets of flux capacitors and \( L \)-products of stars with cycles.

Let \( G \) be a graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( A = \{0,1\} \). A labeling \( f: V(G) \to A \) induces a partial edge labeling \( f^*: E(G) \to A \) defined by \( f^*((u, v)) = f(u) \) if and only if \( f(u) = f(v) \) for each edge \( (u, v) \in E(G) \). For \( i \in A \), let \( \text{v}_f(i) = \text{card} \{v \in V(G) : f(v) = i\} \) and \( \text{e}_f(i) = \text{card} \{e \in E(G) : f^*(e) = i\} \). A labeling \( f \) of \( G \) is said to be friendly if \( |\text{v}_f(0) – \text{v}_f(1)| \leq 1 \). The balance index set of the graph \( G \), \( \text{BI}(G) \), is defined as \( \{|\text{e}_f(0) – \text{e}_f(1)| : \text{the vertex labeling } f \text{ is friendly}\} \). We determine the balance index sets of Halin graphs of stars and double stars.

For a graph \( G \), the expression \( G \overset{v}{\rightarrow} (a_1, \ldots, a_r) \) means that for any \( r \)-coloring of the vertices of \( G \) there exists a monochromatic \( a_i \)-clique in \( G \) for some color \( i \in \{1, \ldots, r\} \). The vertex Folkman numbers are defined as \( F_v(a_1, \ldots, a_r; q) = \text{min}\{|V(G)| : G \overset{v}{\rightarrow} (a_1, \ldots, a_r) \text{ and } K_q \not\subseteq G\} \). Of these, the only Folkman number of the form \( F(\underbrace{2, \ldots, 2}; r – 1) \) which has remained unknown up to this time is \( F_v(2, 2, 2, 2, 2; 4) \).

We show here that \( F_v(2, 2, 2, 2, 2; 4) = 16 \), which is equivalent to saying that the smallest \( 6 \)-chromatic \( K_4 \)-free graph has \( 16 \) vertices. We also show that the sole witnesses of the upper bound \( F_v(2, 2, 2, 2, 2; 4) \leq 16 \) are the two Ramsey \( (4, 4) \)-graphs on \( 16 \) vertices.

We give cyclic constructions for loop designs with block size \( k = 3, 4, \text{ and } 5 \), and all values of \( v \), and we thereby determine the \((v, \lambda)\) spectrum for LDs with these block sizes. For \( k = 3, 5 \) the \((v, \lambda)\) spectrum for LDs is the same as that for cyclic LDs, but this is not true for \( k = 4 \).