Colorings generated by monotone properties

From MaRDI portal





Let \(Q\) be some graph property and let \(G\) with \(| V_G| =n\) be a graph satisfying the property \(Q\). Color the edges of \(G\) black and color an edge \(e\) of the complement of \(G\) red if \(G+e\) satisfies the property \(Q\) and blue otherwise. Thus, we have a red-blue-black coloring of the edges of a complete graph \(K_n\), where the black subgraph is restricted by the property \(Q\). Furthermore denote by \(P(k,b,Q)\) the least \(n\) such that any red-blue-black coloring of \(K_n\) has either a \(k\) element red clique or a \(b\) element blue clique. It is a Ramsey type problem. For the class of triangle-free graphs Vina and Fajtlowicz showed that \(P(k,k,K_3)\sim k^3\) and they conjectured with Erdős that for \(K_r\)-free graphs the best lower bound for \(P(k,k,K_r)\) should be at most \(k^r\) for all \(r>3\). The authors disprove this conjecture by showing that for random graphs the lower bound for \(r=4\) is \(\Omega(k^5)\) and is exponential on \(k\) for all \(r\geq 5\). Moreover, the last lower bound is best possible. They also obtain an exponential lower bound for \(P(k,k,C_4)\) for the class of \(C_4\)-free graphs.











This page was built for publication: Colorings generated by monotone properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4379726)