http://openproblemgarden.org/op/bounded_colorings_for_planar_graphs Comments for "Bounded colorings for planar graphs" en http://openproblemgarden.org/op/bounded_colorings_for_planar_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/alon">Alon</a>; <a href="/category/ding_guoli">Ding</a>; <a href="/category/oporowski_bogdan">Oporowski</a>; <a href="/category/vertigan_dirk">Vertigan</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/topological_graph_theory">Topological G.T.</a> » <a href="/category/coloring_1">Coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp; Does there exists a fixed function <img class="teximage" src="/files/tex/e5839c90f2b5ca6fe2f58de668c9549b3ad831bd.png" alt="$ f : {\mathbb N} \rightarrow {\mathbb N} $" /> so that every <a href="http://en.wikipedia.org/wiki/planar graph">planar</a> graph of maximum degree <img class="teximage" src="/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png" alt="$ d $" /> has a partition of its vertex set into at most three sets <img class="teximage" src="/files/tex/4743659cb13aa2fd42df6291dc9839397a771197.png" alt="$ \{V_1,V_2,V_3\} $" /> so that for <img class="teximage" src="/files/tex/a551cf18cf10c10840b4155cdb12c330c8fec96b.png" alt="$ i=1,2,3 $" />, every component of the graph induced by <img class="teximage" src="/files/tex/af854be1f03aac481e0a165c3908976d4b5b0aa0.png" alt="$ V_i $" /> has size at most <img class="teximage" src="/files/tex/eb1c96d175a846e74b707abbc2eabf3ea4a2d7b2.png" alt="$ f(d) $" />? </div> </tr></td> </table> </td> </tr> </table> Alon, Noga Ding, Guoli Oporowski, Bogdan Vertigan, Dirk coloring partition planar graph Graph Theory Topological Graph Theory Coloring http://openproblemgarden.org/op/bounded_colorings_for_planar_graphs#comment Wed, 23 May 2007 13:24:28 +0200 mdevos 338 at http://openproblemgarden.org