Conjecture on the six-colour two-colour connectivity function

Let n,kNn,k \in \mathbb{N}, with nn sufficiently large compared to kk.

The conjecture. The maximum order of a kk-connected subgraph using at most two colours in every 66-colouring of KnK_n satisfies

m(n,6,2,k)=3n4O(k).m(n,6,2,k) = \frac{3n}{4} - O(k).

This is the conjectured asymptotic value for the case r=6r=6; the paper notes that the corresponding value is known up to a factor of 22 in general, while the case r=5r=5 has already been determined asymptotically.

Sources & referencesView supporting material

Primary source

Henry Liu, Robert Morris and Noah Prince, “Highly connected multicoloured subgraphs of multicoloured graphs”, arXiv:math/0702369 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.