Open Problem Garden - Multicolour Erdős--Hajnal Conjecture - Comments http://garden.irmacs.sfu.ca/op/multicolour_erdos_hajnal_conjecture Comments for "Multicolour Erdős--Hajnal Conjecture" en Multicolour Erdős--Hajnal Conjecture http://garden.irmacs.sfu.ca/op/multicolour_erdos_hajnal_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/erdos">Erdos</a>; <a href="/category/hajnal">Hajnal</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/extremal_graph_theory">Extremal G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every fixed <img class="teximage" src="/files/tex/bf9a9dbad620e3800b95f9120dc9a950b967bbfd.png" alt="$ k\geq2 $" /> and fixed colouring <img class="teximage" src="/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png" alt="$ \chi $" /> of <img class="teximage" src="/files/tex/552f009361444261d52e6cc961a905f4d26ad439.png" alt="$ E(K_k) $" /> with <img class="teximage" src="/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png" alt="$ m $" /> colours, there exists <img class="teximage" src="/files/tex/d572eb4a7102086da01f1eaefee455fa2bce9456.png" alt="$ \varepsilon&gt;0 $" /> such that every colouring of the edges of <img class="teximage" src="/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png" alt="$ K_n $" /> contains either <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> vertices whose edges are coloured according to <img class="teximage" src="/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png" alt="$ \chi $" /> or <img class="teximage" src="/files/tex/7bf7473b27385145f7e4eb3c462a5f2a27198913.png" alt="$ n^\varepsilon $" /> vertices whose edges are coloured with at most <img class="teximage" src="/files/tex/ac0b25768e50cc2e9a824d01affc6ab439d8382c.png" alt="$ m-1 $" /> colours. </div> </tr></td> </table> </td> </tr> </table> Erdos, Paul Hajnal, Andras ramsey theory Graph Theory Extremal Graph Theory http://garden.irmacs.sfu.ca/op/multicolour_erdos_hajnal_conjecture#comment Thu, 10 Oct 2019 11:02:52 +0200 Jon Noel 60042 at http://garden.irmacs.sfu.ca