If the vertices of a graph $G$ are colored with $k$ colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then $G$ is said to be equitably $k$-colorable. Let $|G|$ denote the number
of vertices of $G$ and $Delta=Delta(G)$ the maximum degree of a vertex in $G$. We prove that a graph $G$ of order at least 6 is equitably $Delta$-colorable if $G$ satisfies $(|G|+1)/3 leq Delta < |G|/2$ and none of its components is a $K_{Delta +1}$.
A near-factor of a finite simple graph $G$ is a matching that saturates all vertices except one. A graph $G$ is said to be near-factor-critical if the deletion of any vertex from $G$ results in a subgraph that has a near-factor. We prove that a conne
cted graph $G$ is near-factor-critical if and only if it has a perfect matching. We also characterize disconnected near-factor-critical graphs.
Let $m$, $n$, and $k$ be integers satisfying $0 < k leq n < 2k leq m$. A family of sets $mathcal{F}$ is called an $(m,n,k)$-intersecting family if $binom{[n]}{k} subseteq mathcal{F} subseteq binom{[m]}{k}$ and any pair of members of $mathcal{F}$ have
nonempty intersection. Maximum $(m,k,k)$- and $(m,k+1,k)$-intersecting families are determined by the theorems of ErdH{o}s-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, and $m$ sufficiently large.
Let G be a simple graph. A coloring of vertices of G is called (i) a 2-proper coloring if vertices at distance 2 receive distinct colors; (ii) an injective coloring if vertices possessing a common neighbor receive distinct colors; (iii) a square colo
ring if vertices at distance at most 2 receive distinct colors. In this paper, we study inequalities of Nordhaus-Guddam type for the 2-proper chromatic number, the injective chromatic number, and the square chromatic number.
