2016/08/23 by Monika Rosicka, Rosicka, Monika, Simone Severini +1
Engineering · Computer Science · #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1608.06661
We study the value of unique games as a graph-theoretic parameter. This is obtained by labeling edges with permutations. We describe the classical value of a game as well as give a necessary and sufficient condition for the existence of an optimal assignment based on a generalisation of permutation graphs and graph bundles. In considering some special cases, we relate XOR games to EDGE BIPARTIZATION, and define an edge-labeling with permutations from Latin squares.