http://openproblemgarden.org/op/good_edge_labelings Comments for "Good Edge Labelings" en http://openproblemgarden.org/op/good_edge_labelings#comment-7807 <p>Mehrabian, Mitsche, and Pralat showed that any <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />-vertex graph with a good edge-labelling has at most <img class="teximage" src="/files/tex/7d595342fb82610949af2c23b2c6990ccf60045e.png" alt="$ n \log_2 n $" /> edges, and that for each <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> there is an <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />-vertex graphs with a good edge-labelling having <img class="teximage" src="/files/tex/c363ff9b512154d396e8178ecd55255571da954a.png" alt="$ n \log_2 n - O(n) $" /> edges.</p> <p>http://arxiv.org/abs/1211.2641</p> Sat, 16 Feb 2013 12:06:12 +0100 Anonymous comment 7807 at http://openproblemgarden.org http://openproblemgarden.org/op/good_edge_labelings <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/araujo_julio">Araújo</a>; <a href="/category/cohen_nathann">Cohen</a>; <a href="/category/giroire_frederic_0">Giroire</a>; <a href="/category/havet_frederic">Havet</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/labeling">Labeling</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp; What is the maximum edge density of a graph which has a good edge labeling? </div> <p>We say that a graph is <em>good-edge-labeling critical</em>, if it has no good edge labeling, but every proper subgraph has a good edge labeling.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every <img class="teximage" src="/files/tex/88cd640bb1356a23eb073fd0b147a9a1bca21999.png" alt="$ c&lt;4 $" />, there is only a finite number of good-edge-labeling critical graphs with average degree less than <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" />. </div> </tr></td> </table> </td> </tr> </table> Araújo, Julio Cohen, Nathann Giroire, Frédéric Havet, Frédéric good edge labeling, edge labeling Graph Theory Coloring Labeling http://openproblemgarden.org/op/good_edge_labelings#comment Thu, 30 Jun 2011 19:55:01 +0200 DOT 37323 at http://openproblemgarden.org