The conjecture on the complementary bounding function of the almost identity function

About 13 years old · traced to

Let gg be the almost identity function

g(x)={3for x=2,xfor x>2.g(x)=\begin{cases} 3 & \text{for } x=2,\\ x & \text{for } x>2. \end{cases}

For a graph GG, let α(G)\alpha(G) be its independence number and let θ(G)\theta(G) be its minimum clique-cover number. The complementary bounding function g∗g^* is the optimal function bounding θ(G)\theta(G) in terms of α(G)\alpha(G) for graphs whose chromatic number is bounded by g(ω(G))g(\omega(G)). The conjecture on g∗g^*.

g∗(x)=⌊85x⌋.g^*(x)=\left\lfloor\frac{8}{5}x\right\rfloor.

The statement is suggested by the preceding upper bound and is presented as a conjectural formula; the supplied text gives no resolution, so it is recorded as open.

References

Primary source

András Gyárfás, Zhentao Li, Raphael Machado, András Sebo, Stéphan Thomassé and Nicolas Trotignon, “Complements of nearly perfect graphs”, arXiv:1304.2862 (2013).

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.