http://openproblemgarden.org/op/high_connectivity_no_k_n Comments for "Highly connected graphs with no K_n minor" en http://openproblemgarden.org/op/high_connectivity_no_k_n <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/thomas">Thomas</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/basic_graph_theory">Basic G.T.</a> » <a href="/category/minors">Minors</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Is it true for all <img class="teximage" src="/files/tex/90df48fa9e1e2158a5da469f1fb382d91bf47483.png" alt="$ n \ge 0 $" />, that every sufficiently large <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />-<a href="http://en.wikipedia.org/wiki/connectivity (graph theory)">connected</a> graph without a <a href="http://en.wikipedia.org/wiki/complete graph"><img class="teximage" src="/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png" alt="$ K_n $" /></a> <a href="http://en.wikipedia.org/wiki/minor (graph theory)">minor</a> has a set of <img class="teximage" src="/files/tex/9ed6ca429bf7a035c85bba441d0e1299c0af67dc.png" alt="$ n-5 $" /> vertices whose deletion results in a <a href="http://en.wikipedia.org/wiki/planar graph">planar graph</a>? </div> </tr></td> </table> </td> </tr> </table> Thomas, Robin connectivity minor Graph Theory Basic Graph Theory Minors http://openproblemgarden.org/op/high_connectivity_no_k_n#comment Sat, 10 Mar 2007 14:40:37 +0100 mdevos 153 at http://openproblemgarden.org