Some new characterizations of graph colorability and of blocking sets of projective spaces (Q405185)

Summary: 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\in F_q^V\) of \(G\). Here, \(x\) is called odd if there is an odd number of partitions \(\pi=\{V_1,V_2,\dots,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 \(\sum_{v\in V_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.