http://openproblemgarden.org/op/coloring_squares_of_hypercubes Comments for "Coloring squares of hypercubes" en http://openproblemgarden.org/op/coloring_squares_of_hypercubes#comment-2490 <p>Actually, the conjecture is disproved by <img class="teximage" src="/files/tex/62f4d81345e7050574d109ce5303612dd37a792c.png" alt="$ 13 \le \chi(Q_8^{(2)}) \le 14 $" />, obtained independently by Hougardy in 1991 [1] and Royle in 1993 [2, Section 9.7]. Moreover, although not fully determined, it is known that <img class="teximage" src="/files/tex/3f7d5b6ce3b3879fc7b0c63266d091c593d945bc.png" alt="$ \chi(Q_d^{(2)}) $" /> asymptotically attains the lower bound, as <img class="teximage" src="/files/tex/58fb1cf658d48f5795b30975a70e437ace272896.png" alt="$ \lim_{d \to \infty}\frac{\chi(Q_d^{(2)})}{d}=1 $" />, proven by Ostergard in 2004 [3].</p> <p>There are also several results on <img class="teximage" src="/files/tex/0c5b5cc0595928b9338efde7ce33e14803338bb8.png" alt="$ \chi(Q_d^{(k)}) $" /> for general <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />, and in particular on <img class="teximage" src="/files/tex/46f7349f6c423c37a423f159131771ea7acdde5e.png" alt="$ \chi(Q_d^{(3)}) $" /> [3,4]. </p> <p>[1] G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1 Borsuk problem in low dimensions, in: H. Alt (Ed.), Computational Discrete Mathematics, Springer, Berlin, 2001, 159-171.</p> <p>[2] T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995.</p> <p>[3] P.R.J. Ostergard, On a Hypercube coloring problem, J. Combin. Theory A 108 (2004), 199-204.</p> <p>[4] H.Q. Ngo, D.-Z. Du, R.L. Graham, New bounds on a hypercube coloring problem, Inform. Process. Lett. 84 (2002), 265-269.</p> Wed, 10 Dec 2008 01:44:04 +0100 pgregor comment 2490 at http://openproblemgarden.org http://openproblemgarden.org/op/coloring_squares_of_hypercubes <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/wan_peng_jun">Wan</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/coloring">Coloring</a> » <a href="/category/vertex_coloring">Vertex coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a simple graph, we let <img class="teximage" src="/files/tex/01ee94b72b2ebb3db43dd18da622735b37e51c3a.png" alt="$ G^{(2)} $" /> denote the simple graph with vertex set <img class="teximage" src="/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png" alt="$ V(G) $" /> and two vertices adjacent if they are distance <img class="teximage" src="/files/tex/c85600bf8f9ebbf7fb34960b0d43ecec5afc4fb7.png" alt="$ \le 2 $" /> in <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; <img class="teximage" src="/files/tex/926a7d4eb7afdf8197ff1121f017d56c061947b8.png" alt="$ \chi(Q_d^{(2)}) = 2^{ \lfloor \log_2 d \rfloor + 1} $" />. </div> </tr></td> </table> </td> </tr> </table> Wan, Peng-Jun coloring hypercube Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/coloring_squares_of_hypercubes#comment Wed, 21 Nov 2007 08:32:24 +0100 mdevos 711 at http://openproblemgarden.org