Some new characterizations of graph colorability and of blocking sets of projective spaces
The electronic journal of combinatorics, Tome 21 (2014) no. 2
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,\dotsc,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.
DOI :
10.37236/3767
Classification :
05C15, 51E21, 91A46
Mots-clés : graph coloring, switching games, blocking sets
Mots-clés : graph coloring, switching games, blocking sets
Affiliations des auteurs :
Uwe Schauz 1
@article{10_37236_3767,
author = {Uwe Schauz},
title = {Some new characterizations of graph colorability and of blocking sets of projective spaces},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/3767},
zbl = {1300.05110},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3767/}
}
Uwe Schauz. Some new characterizations of graph colorability and of blocking sets of projective spaces. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3767
Cité par Sources :