http://openproblemgarden.org/op/goldbergs_conjecture Comments for "Goldberg's conjecture" en http://openproblemgarden.org/op/goldbergs_conjecture#comment-34730 <p>http://plms.oxfordjournals.org/content/106/4/703</p> <p>--Stephen</p> Wed, 05 Jun 2013 19:24:42 +0200 SAC comment 34730 at http://openproblemgarden.org http://openproblemgarden.org/op/goldbergs_conjecture#comment-6380 <p>Stiebitz et al(2006), Yu(2008) and Kurt(2009) has separately shown <img class="teximage" src="/files/tex/78673d0565f76d617f188ce39a8262acf377ab6a.png" alt="$ \chi&#039;(G) \geq \Delta+\sqrt{\Delta/2} $" /> implies Goldberg Conjecture. While Yu's method gives a methodological approach to the general problem, Kurt provides a very short and elementary proof. </p> <p>Scheide (2008) has shown <img class="teximage" src="/files/tex/0fd6662693bc078df57e019ba9b164c25da5f56b.png" alt="$ \chi&#039;(G)&gt;\frac{15}{14}\Delta+\frac{12}{14} $" /> implies the Goldberg Conjecture. </p> <p>Kurt(2009) has shown <img class="teximage" src="/files/tex/7951223be5a9ed9e5242f5ee6328b67d3b2c61bc.png" alt="$ \chi&#039;(G)&gt;\frac{17}{16}\Delta+\frac{14}{16} $" /> implies the Goldberg Conjecture.</p> Fri, 06 Feb 2009 09:28:43 +0100 Anonymous comment 6380 at http://openproblemgarden.org http://openproblemgarden.org/op/goldbergs_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/goldberg_mark_k">Goldberg</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>The <em>overfull parameter</em> is defined as follows: <img class="teximage" src="/files/tex/d2391343543ce03d861e6eb2f4985d52e309525d.png" alt="\[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]" /></p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> satisfies <img class="teximage" src="/files/tex/688f47d207abb99bb15f8fc2353553cf3904fc1d.png" alt="$ \chi&#039;(G) \le \max\{ \Delta(G) + 1, w(G) \} $" />. </div> </tr></td> </table> </td> </tr> </table> Goldberg, Mark K. edge-coloring multigraph Graph Theory Coloring Edge coloring http://openproblemgarden.org/op/goldbergs_conjecture#comment Sat, 04 Oct 2008 00:11:24 +0200 mdevos 2242 at http://openproblemgarden.org