Average complexity of graph coloring using backtracking

I coded a backtracking algorithm to color graphs, here is the code in python:

def neighbors(G, k):  # return the list of the neighbors of k in G
    neigh = []
    for i in range(shape(G)[0]):
        if G[k][i]:
            neigh.append(i)
    return neigh


def backtrack_color(G, colors, k=0, max_col=6):
    if k == shape(G)[0]:
        return True, colors
    for i in range(max_col):
        colors[k] = i
        if not i in [colors[n] for n in neighbors(G, k)]:
            if backtrack_color(G, colors, k + 1, max_col)[0]:
                return True, colors
    colors[k] = -1
    return False, colors

I found the worst case time complexity (O(m^n) where m is max_col and n the number of vertices of G) but I need the average case time complexity and I cannot find it.

Could anyone help?

Also first post so sorry if I made any mistake