← All problems

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

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
  1. 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.