Some new characterizations of graph colorability and of blocking sets of projective spaces

Let G = (V, E) be a graph and q be an odd prime power. We prove that G possess a proper vertex coloring with q colors if and only if there exists an odd vertex labeling x ∈ F^V_q of G. Here x is called odd if there is an odd number of partitions that π = {V₁,V₂,...,V_t} of V whose blocks V_i are G-bipartite and x-balanced, i.e., such that G|V_i is connected and bipartite, and ∑_v∈Vi x_vI = 0. Other new characterizations concern edge colorability of graphs and, on a more general level, blocking sets of projective spaces. Some of these characterizations are formulated in terms of a new switching game.