Non-realizability of the triple (3,5,6) for graph parameters

Let GG be a graph, and write \a0ω(G)\a0\omega(G) for its clique number, \a0χ(G)\a0\chi(G) for its chromatic number, and \a0χρ(G)\a0\chi_{\rho}(G) for its packing chromatic number. Non-realizability conjecture. There is no graph GG such that

ω(G)=3,χ(G)=5,χρ(G)=6.\omega(G)=3,\qquad \chi(G)=5,\qquad \chi_{\rho}(G)=6.

Equivalently, the triple (3,5,6)(3,5,6) is not realizable. The conjecture concerns whether the lower bound in the table of known values for the auxiliary function m(a,b)m(a,b) can be improved; the supplied text gives no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Boštjan Brešar, Sandi Klavžar, Douglas F. Rall and Kirsti Wash, “Packing chromatic number versus chromatic and clique number”, arXiv:1707.04910 (2017).

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.