http://openproblemgarden.org/op/circular_flow_number_of_regular_class_1_graphs Comments for "Circular flow number of regular class 1 graphs" en http://openproblemgarden.org/op/circular_flow_number_of_regular_class_1_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/steffen_eckhard">Steffen</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/flows">Nowhere-zero flows</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>A nowhere-zero <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-flow <img class="teximage" src="/files/tex/fb078c6d01999e5636dd47666ead70708553c4eb.png" alt="$ (D(G),\phi) $" /> on <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is an orientation <img class="teximage" src="/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png" alt="$ D $" /> of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> together with a function <img class="teximage" src="/files/tex/714f40c44f7fd872f2e8b521309f1fa7c9df87d1.png" alt="$ \phi $" /> from the edge set of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> into the real numbers such that <img class="teximage" src="/files/tex/ebf099d2080153f16fd9a353474abc3987a85d84.png" alt="$ 1 \leq |\phi(e)| \leq r-1 $" />, for all <img class="teximage" src="/files/tex/730c5d64c8d749c640adc18eb493c641ff1addc9.png" alt="$ e \in E(G) $" />, and <img class="teximage" src="/files/tex/71d8476b6df9f6d06c1db9e2b6c0e2b1fa3bf798.png" alt="$ \sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G) $" />. The circular flow number of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is inf<img class="teximage" src="/files/tex/a1e0cf600eb20371951dda7d814be2d8fba49c0c.png" alt="$ \{ r | G $" /> has a nowhere-zero <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-flow <img class="teximage" src="/files/tex/61d6d5a1674a181e12e2feefc99ee78fac818369.png" alt="$ \} $" />, and it is denoted by <img class="teximage" src="/files/tex/2feb15c852076fe47e3d773821dc8e5df41c8ba1.png" alt="$ F_c(G) $" />.</p> <p>A graph with maximum vertex degree <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> is a class 1 graph if its edge chromatic number is <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/f9082ade09146d7aa9994735ba4ad788d0583b0c.png" alt="$ t \geq 1 $" /> be an integer and <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> a <img class="teximage" src="/files/tex/da4d60d92c98256f762bb69398437f3914ef0fa6.png" alt="$ (2t+1) $" />-regular graph. If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a class 1 graph, then <img class="teximage" src="/files/tex/35f6f6ba01e2a1f8f2c867888c086731d735cc74.png" alt="$ F_c(G) \leq 2 + \frac{2}{t} $" />. </div> </tr></td> </table> </td> </tr> </table> Steffen, Eckhard nowhere-zero flow, edge-colorings, regular graphs Graph Theory Coloring Nowhere-zero flows http://openproblemgarden.org/op/circular_flow_number_of_regular_class_1_graphs#comment Wed, 05 Aug 2015 15:28:29 +0200 Eckhard Steffen 59994 at http://openproblemgarden.org