Consider the problem of removing an edge from $K_q$ and asking about
non-isomorphic vertex colorings using at most $N$ colors. This requires
the cycle index $Z(G_q)$ of the group permuting the vertices. There are
two possibilities. Fix the vertices $u$ and $v$ where the edge has been
removed or flip them. The remaining $q-2$ vertices are not
distinguishable and are permuted by the symmetric group $S_{q-2}$ with
cycle index $Z(S_{q-2}).$ It follows that the cycle index $Z(G_q)$ is
given by
$$Z(G_q) = \frac{1}{2} (a_1^2+a_2) Z(S_{q-2}).$$
When $q=5$ we have
$$Z(G_5) = \frac{1}{2} (a_1^2+a_2)
\frac{1}{6} (a_1^3 + 3a_1 a_2 + 2a_3).$$
Remark. Adhering to the question as stated and supposing that the
edge was between vertices $1$ and $5$ we get the permutations
$$12345, 12435, 13245, 13425, 14235, 14325,
\\ 52341, 52431, 53241, 53421, 54231, 54321.$$
We then factor these into cycles to get the cycle index. For example,
$53241$ yields $a_1 a_2^2.$ Burnside says we have to be constant on
the cycles and here we have three of them and may choose a color for
each.
Therefore we get for colorings with at most $N$ colors for $q=5$
$$\frac{1}{12} (N^2 + N) (N^3 + 3 N^2 + 2N)$$
which is the sequence
$$1, 12, 60, 200, 525, 1176, 2352, 4320, 7425, 12100, \ldots$$
In particular using at most three colors gives
$$\bbox[5px,border:2px solid #00A000]{
60}$$
colorings.
Returning to the general problem, as an example, here is the cycle index
for $K_7$ minus an edge:
$$Z(G_7) = {\frac {{a_{{1}}}^{7}}{240}}
+{\frac {11\,{a_{{1}}}^{5}a_{{2}}}{240}}
+{\frac {5\,{a_{{1}}}^{3}{a_{{2}}}^{2}}{48}}
+1/12\,{a_{{1}}}^{4}a_{{3}}+1/6\,{a_{{1}}}^{2}a_{{2}}a_{{3}}
\\ +1/16\,a_{{1}}{a_{{2}}}^{3}
+1/8\,{a_{{1}}}^{3}a_{{4}}+1/8\,a_{{1}}a_{{2}}a_{{4}}
\\+1/12\,{a_{{2}}}^{2}a_{{3}}
+1/10\,{a_{{1}}}^{2}a_{{5}}+1/10\,a_{{2}}a_{{5}}.$$
With the number of permutations having $k$ cycles in the symmetric group
$S_n$ being given by ${n\brack k}$ we get the closed form
$$\bbox[5px,border:2px solid #00A000]{
\frac{1}{2(q-2)!} (N+N^2) \sum_{p=0}^{q-2} {q-2\brack p} N^p.}$$
If you are interested in exploring these cycle indices there is the following Maple code.
with(combinat);
pet_cycleind_symm :=
proc(n)
local l;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_cycleind_kn_minus_edge :=
proc(q)
expand(1/2*(a[1]^2+a[2])*pet_cycleind_symm(q-2));
end;
COLS :=
proc(q, N)
option remember;
local subl, p;
if q = 1 then return FAIL fi;
subl := [seq(a[p]=N, p=1..max(2, q-2))];
subs(subl, pet_cycleind_kn_minus_edge(q));
end;
COLSx :=
proc(q, N)
local p;
if q = 1 then return FAIL fi;
1/2/(q-2)!*(N+N^2)*
add(abs(stirling1(q-2,p))*N^p, p=0..q-2);
end;
We can also ask about proper colorings using $k$ colors, where we
require the corresponding orbital chromatic polynomial. These can be
computed by inspection. We need to choose $q-2$ colors for the clique.
These can be combined with either one or two colors for $u$ and $v.$ We
find
$${k\choose q-2} \left({k-(q-2)\choose 1} + {k-(q-2)\choose
2}\right)
\\ = \frac{1}{2(q-2)!} k(k-1)(k-2)\cdots(k-(q-3)) \times
(k-(q-2)) (2+k-1-(q-2))
\\ = \frac{1}{2(q-2)!} k(k-1)(k-2)\cdots
(k-(q-4))(k-(q-3))^2 (k-(q-2)).$$
This matches the output from the OCP
algorithm.
Concluding remark. It is also possible to count non-isomorphic,
non-proper colorings where exactly $N$ colors are used (all colors
present) using Stirling numbers. This yields
$$\bbox[5px,border:2px solid #00A000]{
\frac{N!}{2(q-2)!}
\sum_{p=0}^{q-2} {q-2\brack p}
\left({p+1\brace N} + {p+2\brace N}\right).}$$
This is verified here.
COLSall :=
proc(q, N)
local M;
if q = 1 then return FAIL fi;
add(binomial(N,M)*(-1)^(N-M)*COLSx(q, M),
M=1..N);
end;
COLSallx :=
proc(q, N)
local p;
if q = 1 then return FAIL fi;
N!/2/(q-2)!*
add(abs(stirling1(q-2,p))*
(stirling2(p+1,N)+stirling2(p+2,N)), p=0..q-2);
end;
