http://openproblemgarden.org/op/strong_edge_colouring_conjecture Comments for "Strong edge colouring conjecture" en http://openproblemgarden.org/op/strong_edge_colouring_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/erdos">Erdos</a>; <a href="/category/nesetril">Nesetril</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/edge_coloring">Edge coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>A strong edge-colouring of a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index <img class="teximage" src="/files/tex/49d3ff4a6ed15117cb09ee85a90ffe2d63936c0e.png" alt="$ s\chi&#039;(G) $" /> is the minimum number of colours in a strong edge-colouring of <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/a63811dfccf4e3128accc3daca7041ff5097e2a2.png" alt="$$s\chi&#039;(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$" /> <img class="teximage" src="/files/tex/987d7e1dcf43bb92750a5d1dffe79abc224035c2.png" alt="$$s\chi&#039;(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&amp;\text{if $\Delta$ is odd.}$$" /> </div> </tr></td> </table> </td> </tr> </table> Erdos, Paul Nesetril, Jaroslav Graph Theory Coloring Edge coloring http://openproblemgarden.org/op/strong_edge_colouring_conjecture#comment Fri, 01 Mar 2013 18:20:23 +0100 fhavet 46475 at http://openproblemgarden.org