Edit (2020-07-15): Since the discussion below is perhaps a bit long, let me condense my question to the following
Short form of the question: Let $G$ be a finite graph (undirected and without self-loops), and $0\leq p\leq 1$ be a real number. Is there a standard name for the smallest $n$ for which there exists a probability distribution on the set of all maps $c\colon V(G) \to \{1,\ldots,n\}$ (where $V(G)$ is the vertex set of $G$) such that for every edge $(x,y)$ of $G$ the probability of $c(x)\neq c(y)$ is $\geq p$ (so when $p=1$ this is just the chromatic number of $G$)? Is it discussed somewhere in the literature?
Long version:
Let $G$ be a graph (undirected and without self-loops; and I'll mostly be thinking finite even though the definition doesn't require it), $n$ a natural number (number of colors) and $0\leq p\leq 1$ real. Let us say that $G$ is interactively $n$-colorable with threshold $p$ (for lack of a better term) when Alice and Bob have a strategy in the following game of interactive proof:
The game: Alice and Bob (also collectively known as “the provers”) agree on a strategy in advance, but thenceforth cannot communicate. Vera (also known as “the verifier”) presents each of the provers with a vertex in the graph $G$ and expects an element of $\{1,\ldots,n\}$ (a “color”) in response. Alice and Bob win when they have a strategy which ensures that:
when presented with the same vertex they will always answer the same color,
when presented with vertices connected by an edge in $G$ they will give answers that are distinct with probability $\geq p$ (against any choices made by Vera).
Under the assumptions of local realism (which I make by default), condition (1) requires that Alice and Bob have, in fact, agreed on a choice of color for each vertex, so the game can be simplified to have just one prover who should be able to pick such a choice at random in such a way that each given edge has probability $\geq p$ of having distinct colors. If furthermore $p=1$, this is merely asking that $G$ is, indeed, colorable with $n$ colors (while if $p=0$, the prover(s) win trivially for any graph with $1$ color).
For example, the cycle graph with an odd number $k$ of vertices is interactively $2$-colorable with threshold $1 - \frac{1}{k}$ by choosing a random edge at which to break the coloring.
Let's say that the interactive chromatic number with threshold $p$ of $G$ is the smallest $n$ such that $G$ is interactively $n$-colorable with threshold $p$.
Question: Does this chromatic number have a standard name? (Or equivalently, the sup of the $p$ for which $G$ is colorable for a given $n$.) If so, where can I learn more about it?
Remarks / variants: One reason why I presented it in the form of the interactive game described above is that it admits a quantum variant in which, instead of demanding local realism, we allow Alice and Bob to prepare and share an entangled quantum state (there are possibly nonequivalent ways to define this, though). For $p=1$ this is known as the “quantum chromatic number”, but it makes sense with a more general $p$ as in the case described above. E.g., the triangle graph is quantum interactively colorable with $2$ colors and threshold $\frac{3}{4}$, whereas it is interactively colorable with $2$ colors only up to threshold $\frac{1}{2}$. So I am also interested in knowing of the quantum case has a standard name or has been studied in the literature. (The paper “Non-closure of the set of quantum correlations via graphs” by Dykema, Paulsel and Prakash seems related but doesn't appear to define exactly the concept I just mentioned.) (Also, another point worth mentioning is that if Alice and Bob, instead of a quantum system, have access to an unlimited supply of Popescu-Rohrlich boxes, they can $2$-color any graph with threshold $1$.)
Finally, we could also, instead of fixing $p$ for all vertices, consider not a graph but an edge-weighted graph where each edge is labeled by the threshold for that particular graph. I am also interested in knowing whether this generalization has a name.
