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

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 gg^* 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 gg^*.

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.

Sources & referencesView supporting material

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.