https://www.openproblemgarden.org/op/black_and_white_cycle_conjecture Comments for "Black and White Cycle Conjecture " en https://www.openproblemgarden.org/op/black_and_white_cycle_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/arthur">Arthur</a>; <a href="/category/hoffmann_ostenhof">Hoffmann-Ostenhof</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> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a cubic graph with a nz-<img class="teximage" src="/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png" alt="$ 4 $" />-flow, and let each edge <img class="teximage" src="/files/tex/730c5d64c8d749c640adc18eb493c641ff1addc9.png" alt="$ e \in E(G) $" /> satisfying <img class="teximage" src="/files/tex/a9c40841d6043b14ca9501d156e86164ad3f81e5.png" alt="$ G-e $" /> does not have a nz-<img class="teximage" src="/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png" alt="$ 4 $" />-flow be colored black, and let each edge <img class="teximage" src="/files/tex/730c5d64c8d749c640adc18eb493c641ff1addc9.png" alt="$ e \in E(G) $" /> satisfying <img class="teximage" src="/files/tex/a9c40841d6043b14ca9501d156e86164ad3f81e5.png" alt="$ G-e $" /> has a nz-<img class="teximage" src="/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png" alt="$ 4 $" />-flow be colored white. Then <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> contains a white cycle but not a black cycle.</p> <p><br> <i>Used terminology</i>: nz-<img class="teximage" src="/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png" alt="$ 4 $" />-flow is the abbrevation for nowhere-zero <img class="teximage" src="/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png" alt="$ 4 $" />-flow, a cycle is a connected <img class="teximage" src="/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png" alt="$ 2 $" />-regular graph, a cycle is called black (white) if each edge of the cycle is colored black (white).</p> </div> </tr></td> </table> </td> </tr> </table> Arthur Hoffmann-Ostenhof 3-edge-coloring 4-flow cubic graphs removable edge Graph Theory Coloring Edge coloring https://www.openproblemgarden.org/op/black_and_white_cycle_conjecture#comment Mon, 21 Sep 2026 21:57:03 +0200 arthur 60499 at https://www.openproblemgarden.org