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

At least 20 years old · documented by

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 Aj⊂VA_j\subset V, for j=1,…,∣M∣j=1,\ldots,|M|, such that ∣M∩Aj∣=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.

References

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.