The harmonious chromatic number of a graph. A harmonious colouring is a proper vertex colouring such that any pair of colours appears at most once on adjacent vertices.

The number of positive eigenvalues of the Laplacian matrix of the graph. This is the number of vertices minus the number of connected components of the graph.

The length of a longest path in a graph.

The number of positive values of the symmetric group character corresponding to the partition. For example, the character values of the irreducible representation $S^{(2,2)}$ are $2$ on the conjugacy classes $(4)$ and $(2,2)$, $0$ on the conjugacy classes $(3,1)$ and $(1,1,1,1)$, and $-1$ on the conjugacy class $(2,1,1)$. Therefore, the statistic on the partition $(2,2)$ is $2$.

The Colin de Verdière graph invariant.

The number of distinct eigenvalues of the distance Laplacian of a connected graph.

The hat guessing number of a graph. Suppose that each vertex of a graph corresponds to a player, wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The hat guessing number $HG(G)$ of a graph $G$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ possible colors. Because it suffices that a single player guesses correctly, the hat guessing number of a graph is the maximum of the hat guessing numbers of its connected components.

The disjunction number of a graph. Let $V_n$ be the power set of $\{1,\dots,n\}$ and let $E_n=\{(a,b)| a,b\in V_n, a\neq b, a\cap b=\emptyset\}$. Then the disjunction number of a graph $G$ is the smallest integer $n$ such that $(V_n, E_n)$ has an induced subgraph isomorphic to $G$.

The Prague dimension of a graph. This is the least number of complete graphs such that the graph is an induced subgraph of their (categorical) product. Put differently, this is the least number $n$ such that the graph can be embedded into $\mathbb N^n$, where two points are connected by an edge if and only if they differ in all coordinates.

The number of nonisomorphic vertex-induced subtrees.