Brignall's prime bound conjecture for graphs

Let GG be a graph with V(G)2|V(G)|\geq 2. The prime bound p(G)p(G) is the smallest integer such that GG admits a prime p(G)p(G)-extension; here α(G)\alpha(G) denotes the stability number and ω(G)\omega(G) the clique number. Brignall's prime bound conjecture.

p(G)log2(max(α(G),ω(G))+1).p(G)\leq\left\lceil\log_2\bigl(\max(\alpha(G),\omega(G))+1\bigr)\right\rceil.

This would improve the general upper bound obtained from the number of vertices by replacing V(G)|V(G)| with the larger of the stability and clique numbers. The supplied source does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Abderrahim Boussaïri and Pierre Ille, “Determination of the prime bound of a graph”, arXiv:1301.1157 (2013).

Additional references

2 papers in this index state this conjecture (2011–2013). The statement above is taken from the most recent of them; the others are arXiv:1110.2935.

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.