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

Uwe Schauz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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 ∈ FVq of G. Here x is called odd if there is an odd number of partitions that π = {V1,V2,...,Vt} of V whose blocks Vi are G-bipartite and x-balanced, i.e., such that G|Vi is connected and bipartite, and ∑v∈Vi xvI = 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.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Issue number2
Publication statusPublished - 1 Apr 2014

Cite this