The principal conjecture on clique coverings and stable sets in B-graphs

Let GG be a B-graph, meaning that σv(G)=α(G)\sigma_v(G)=\alpha(G), and suppose that GG has no isolated vertices. Let ωe(G)\omega_e(G) be the greatest natural number such that every edge of GG belongs to a clique of size at least ωe(G)\omega_e(G), and let σv(G)\sigma_v(G) denote the corresponding vertex-stable-set invariant. For every maximum stable set MM,

ωe(G)σv(G)V.\omega_e(G)\sigma_v(G)\leq |V|.

Moreover, there exist disjoint sets AjVA_j\subset V, for j=1,,Mj=1,\ldots,|M|, such that MAj=1|M\cap A_j|=1 for every jj, and G[Aj]G[A_j] is a clique of order ωe(G)\omega_e(G) for every jj. This conjecture is part of the study of bounds relating clique-covering and stable-set invariants; weaker versions are known, but the full assertion is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Isidoro Gitler and Carlos E. Valencia, “On bounds for some graph invariants”, arXiv:math/0510387 (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.