Search

Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around rounding the solution to a Semidefinite Program. However, it is likely that important combinatorial or algebraic insights are needed in order to break the no(1) threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3-coloring of random graphs, and Arora and Ge studied the 3-coloring of graphs with low threshold-rank. In this work, we study graphs that arise from a tensor product, which appear to be novel instances of the 3-coloring problem. We consider graphs of the form H = (V,E) with V = V (K3 G) and E = E(K3 G) s E, where E E(K3 G) is any edge set such that no vertex has more than an -fraction of its edges in E. We show that one can construct H = K3 \times G with V (H) = V (H) that is close to H. For arbitrary G, H satisfies | E(H)Δ E H)| O(\epsilon | E(H)|). Additionally, when G is a mild expander, we provide a 3-coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP-hard to 3-color H. [ABSTRACT FROM AUTHOR]