ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a graph, let n(G)=∣V(G)∣n(G)=|V(G)| denote its order, and let ιg(G)\iota_{\rm g}(G) and ιg′(G)\iota_{\rm g}'(G) denote the game isolation numbers when Dominator and Staller, respectively, start. A graph has no K2K_2-components if none of its connected components is isomorphic to K2K_2. Three-sevenths upper-bound conjecture. For any graph GG with no K2K_2-components,

ιg(G)≤⌈37n(G)⌉ and ιg′(G)≤⌈37n(G)⌉.\iota_{\rm g}(G) \leq \left\lceil\frac{3}{7}n(G)\right\rceil \text{ and } \iota_{\rm g}'(G) \leq \left\lceil\frac{3}{7}n(G)\right\rceil.

The conjecture would improve the proved upper bound ιg(G)≤n(G)/2\iota_{\rm g}(G)\leq n(G)/2 for the isolation game. The bound is supported by examples attaining the three-sevenths value, but no proof is given and the conjecture remains open.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.