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 is an element of F-q(V) of G. Here x is called odd if there is an odd number of partitions pi = {V-1,V-2, . . . , V-t} of V whose blocks V-i are G-bipartite and x-balanced, i.e., such that G vertical bar V-i is connected and bipartite, and Sigma V-v is an element of(i) x(v) = 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.