In this paper, we find necessary and sufficient conditions for the existence of a \(6\)-cycle system of \(K_n – E(R)\) for every \(2\)-regular, not necessarily spanning subgraph \(R\) of \(K_n\).

It is known that the smallest complete bipartite graph which is not \(3\)-choosable has \(14\) vertices. We show that the extremal configuration is unique.

We formalize the intuitive question of coloring the bricks of a wall in such a way that no repetition occurs in any row, nor any vertical line intersects two or more bricks with the same color. We achieve a complete classification up to the least number of required colors, among all dimensions of the walls, and all admitted incidences of the bricks. The involved combinatorial structures (namely, \(regular\) \(walls\)) are a special case of more general structures, which can be interpreted as adjacency matrices of suitable directed hypergraphs. Coloring the bricks is equivalent to coloring the arcs of the corresponding hypergraph. Regular walls seem interesting also for their connections with latin rectangles.

Tutte’s \(3\)-flow conjecture is equivalent to the assertion that there exists an orientation of the edges of a \(4\)-edge-connected, \(5\)-regular graph \(G\)for which the out-flow at each vertex is \(+3\) or \(-3\). The existence of one such orientation of the edges implies the existence of an equipartition of the vertices of \(G\) that separates the two possible types of vertices. Such an equipartition is called mod \(3\)-orientable. We give necessary and sufficient conditions for the existence of mod \(3\)-orientable equipartitions in general \(5\)-regular graphs, in terms of:(i) a perfect matching of a bipartite graph derived from the equipartition;(ii) the sizes of cuts in \(G\).Also, we give a polynomial-time algorithm for testing whether an equipartition of a \(5\)-regular graph is mod \(3\)-orientable.

In this paper, we look at generalizations of Stirling numbers which arise for arbitrary integer sequences and their \(k\)-th powers. This can be seen as a complementary strategy to the unified approach suggested in [9]. The investigations of [3] and [14] present a more algebraically oriented approach to generalized Stirling numbers.

In the first and second sections of the paper, we give the corresponding formulas for the generalized Stirling numbers of the second and first kind, respectively. In the third section, we briefly discuss some examples and special cases, and in the last section, we apply the square case to facilitate a counting approach for set partitions of even size.

In this paper, we give two sufficient conditions for a graph to be type \(1\) with respect to the total chromatic number and prove the following results:

(i) If \(G\) and \(H\) are of type \(1\), then \(G \times H\) is of type \(1\);

(ii) If \(\varepsilon(G) \leq v(G) + \frac{3}{2}\Delta(G) – 4\), then \(G\) is of type \(1\).

We prove several results dealing with various counting functions for partitions of an integer into four squares of equal parity. Some are easy consequences of earlier work, but two are new and surprising. That is, we show that the number of partitions of \(72n+ 60\) into four odd squares (distinct or not) is even.

We prove that if \(G\) is a simple graph of order \(n \geq 3k\) such that \(|N(x) \cup N(y)| \geq 3k\) for all nonadjacent pairs of vertices \(x\) and \(y\), then \(G\) contains \(k\) vertex-independent cycles.

The non-planar vertex deletion or vertex deletion \(vd(G)\) of a graph \(G = (V, E)\) is the smallest non-negative integer \(k\) such that the removal of \(k\) vertices from \(G\) produces a planar graph. Hence, the maximum planar induced subgraph of \(G\) has precisely \(|V| – vd(G)\) vertices. The problem of computing vertex deletion is in general very hard; it is NP-complete. In this paper, we compute the non-planar vertex deletion for the family of toroidal graphs \(C_n \times C_m\).

Let \(K_4\backslash e=…\). If we remove the “diagonal” edge, the result is a \(4\)-cycle. Let \((X,B)\) be a \(K_4\backslash e\) design of order \(n\); i.e., an edge-disjoint decomposition of \(K_n\) into copies of \(K_4\backslash e\). Let \(D(B)\) be the collection of “diagonals” removed from the graphs in \(B\) and \(C(B)\) the resulting collection of \(4\)-cycles. If \(C_2(B)\) is a reassembly of these edges into \(4\)-cycles and \(L\) is the collection of edges in \(D(B)\) not used in a \(4\)-cycle of \(C_2(B)\), then \((X, (C_1(B) \cup C_2(B)), L)\) is a packing of \(K_n\) with \(4\)-cycles and is called a metamorphosis of \((X,B)\). We construct, for every \(n = 0\) or \(1\) (mod \(5\)) \(> 6\), \(n \neq 11\), a \(K_4\backslash e\) design of order \(n\) having a metamorphosis into a maximum packing of \(K_n\) with \(4\)-cycles. There exists a maximum packing of \(K_n\) with \(4\)-cycles, but it cannot be obtained from a \(K_4\backslash e\) design.