For any simple, undirected graph $G=(V,E)$, we denote by $\chi(G)$ the smallest cardinal $\kappa$ such that there is a coloring $c:V \to \kappa$.


We say that $v\neq w\in V$ are *incompatible* if $\{v,w\}\notin E$, and for any coloring $c: V\to \chi(G)$ we have $c(v) \neq c(w)$.


It is easy to see that if $v\neq w\in V$ are incompatible, they must lie in the same connected component of $G$.


What is an example of a graph containing an incompatible pair of vertices?



"Incompatible" pairs with respect to graph coloring
If $R$ is a poset, then a function $C:R\rightarrow R$ is said to be a closure operator if $r\leq C(r)=C(C(r))$ and $(r\leq s)\rightarrow(C(r)\leq C(s))$ whenever $r,s\in R$. We say that a subset $C\subseteq R$ is a closure system if for all $r\in R$, there is a least $s\in C$ where $r\leq s$. If $R$ is a complete lattice, then $C\subseteq R$ is a closure system if and only if $C$ is closed under arbitrary greatest lower bounds including the empty greatest lower bound. ​The closure operators and closure systems on a poset are in a one-to-one correspondence. If $C$ is a closure system, then let $C^{\*}:R\rightarrow R$ be the mapping where if $r\in C$, then $C^{\*}(r)$ is the least element $s$ in $C$ with $r\leq s$. ​Then $C^{\*}$ is a closure operator. Similarly, if $C$ is a closure operator, then define $C^{\*}=\{r\in R\mid r=C(r)\}$. Then $C^{\*}$ is a closure system. Furthermore, if $C$ is a closure operator or closure system, then $C=(C^{\*})^{\*}$.


Suppose that $R,S$ are posets. Then a pair of mappings $f:R\rightarrow S,g:S\rightarrow R$ is said to be a Galois connection if
$s\leq f(r)\leftrightarrow r\leq g(s)$. If $f:R\rightarrow S,g:S\rightarrow R$ is a Galois connection, then the functions $f\circ g,g\circ f$ are closure operators. Furthermore, the maps $f,g$ restrict to order reversing inverse bijections between the closure systems $(f\circ g)^{\*},(g\circ f)^{\*}$.


Suppose that $X,Y$ are sets. Let $R\subseteq X\times Y$ be a relation. Then
define functions $F:P(X)\rightarrow P(Y),G:P(Y)\rightarrow P(X)$ by letting
$F(A)=\{y\in Y\mid\forall x\in A,(x,y)\in R\}$ and
$G(B)=\{x\in X\mid\forall y\in B,(x,y)\in R\}$. Then the functions $F,G$ form a Galois connection.


Let $\lambda$ be a cardinal, and let $V$ be a vertex set. Then define a relation
$R\_{\lambda,V}\subseteq[V]^{2}\times^{V}\lambda$ where if $u,v\in V,u\neq v$ and
$f:V\rightarrow\lambda$ is a function, then $\{u,v\},f)\in R\_{\lambda,V}$ if and only if $f(u)\neq f(v)$. Then from this relation, we define a Galois connection
$F\_{\lambda,V}:P([V]^{2})\rightarrow P(^{V}\lambda),G\_{\lambda,V}:P(^{V}\lambda)\rightarrow P([V]^{2})$ the standard way by setting $F\_{\lambda,V}(R)=\{s\in^{V}\lambda\mid\forall r\in R,(r,s)\in R\_{\lambda,V}\}$ and $G\_{\lambda,V}(S)=\{r\in[V]^{2}\mid\forall s\in S,(r,s)\in R\_{\lambda,V}\}$.


Define closure operators $C\_{\lambda,V}:P([V]^{2})\rightarrow P([V]^{2}),D\_{\lambda,V}:P(^{V}\lambda)\rightarrow P(^{V}\lambda)$ by letting
$C\_{\lambda,V}=G\_{\lambda,V}\circ F\_{\lambda,V},D\_{\lambda,V}=F\_{\lambda,V}\circ G\_{\lambda,V}$.


If $G=(V,E)$, then the following are equivalent:


1. $\chi\_{G}\leq\lambda$.
2. $F\_{\lambda,V}(E)\neq\emptyset$.
3. $C\_{\lambda,V}(E)\neq[V]^{2}$.


We observe that if $\lambda,\mu$ are cardinals with
$\lambda\leq\mu$, then $C\_{\mu,V}(E)\subseteq C\_{\lambda,V}(E)$.


In particular, if $\lambda$ is a cardinal and $F\_{\lambda,V}(E)\neq\emptyset$, then every edge in $C\_{\lambda,V}(E)\setminus E$ is an incompatible edge. In particular, the graph $(V,E)$ has an incompatible edge if and only if $E$ is non-closed and non-dense.


**Finite chromatic number examples**


If $(V,E)$ is a connected bipartite graph with bipartition $A,B$, then
$C\_{2,V}(E)=\{\{a,b\}\mid a\in A,b\in B\}$. Connected incomplete bipartite graphs therefore have incompatible edges.


More generally, as was mentioned by Tony Huynh in the comments, we say that a graph $G=(V,E)$ is uniquely colorable with $k$ colors if it is not colorable with $k-1$ colors and where there is only one coloring $f:V\rightarrow k$ up to permutations (i.e. if $f,g:V\rightarrow k$ are colorings, then there is a permutation $h\in S\_{k}$ with $g=h\circ f$). Every complete graph is uniquely colorable. Furthermore, one can easily construct new uniquely colorable graphs from old uniquely colorable graphs. Suppose that $(V,E)$ is a uniquely colorable graph with $k$-colors. Let $f:V\rightarrow k$ be the unique (up-to-permutation) coloring of $(V,E)$. Then let $v$ be a vertex with $v\not\in V$. Then let $v\_{1},\dots,v\_{k}$ be vertices where $f(v\_{1}),\dots,f(v\_{k})$ are distinct. Then $(V\cup\{v\},E\cup\{\{v,v\_{i}\}\mid 1\leq i\leq k\})$ is also uniquely colorable. In particular, every [k-tree](https://en.wikipedia.org/wiki/K-tree) is uniquely colorable with k colors.


If $(V,E)$ is a uniquely colorable graph with $k$ colors, and $f:V\rightarrow k$ is the unique coloring, then whenever $\{u,v\}\not\in E$ and $f(u)\neq f(v)$, the edge $\{u,v\}$ is incompatible with $(V,E)$. In particular, if $$|E|<|V|\cdot(|V|-1)/2-\sum\_{i=0}^{k-1}|f^{-1}[\{i\}]|\cdot(|f^{-1}[\{i\}]|-1)/2,$$
then there is some edge $\{u,v\}$ incompatible with $(V,E)$.


**Deletion-contraction**


There is a deletion-contraction formula for the number of $k$-colorings of a graph, and this deletion-contraction formula applies for infinite graphs as well with infinitely many colorings.


Suppose that $G=(V,E)$ is a graph. If $\simeq$ is an equivalence relation on $V$, then let $G/\simeq$ denote the graph with vertex set $V/\simeq$ and with edge set $E/\simeq=\{\{[u],[v]\}\mid\{u,v\}\in E,u\not\simeq v\}$.
If $\{u,v\}$ is a pair, then let $G/\{u,v\}$ denote the graph $G/\simeq$ where $x\simeq y$ if and only if $x=y$ or $\{x,y\}=\{u,v\}$.


If $(V,E)$ is a graph where $u,v,\in V,u\neq v,\{u,v\}\not\in E$, then by using the same notation as before, we define a function
$$L:F\_{k,V}(E\cup\{\{u,v\}\})\cup F\_{k,V/\{u,v\}}(E/\{u,v\})\rightarrow F\_{\lambda,V}(E)$$
by letting $L(f)=f$ whenever $f\in F\_{k,V}(E\cup\{\{u,v\}\})$ and
$L(f)=f\circ\pi$ where $\pi:V\rightarrow V/\{u,v\}$ is the quotient mapping.


Therefore, $F\_{k,V}(E\cup\{\{u,v\}\})=F\_{k,V}(E)$ if and only if
$F\_{k,V/\{u,v\}}(E/\{u,v\})=\emptyset$. In particular, if $\{u,v\}\in[V]^{2}\setminus E$, then $\{u,v\}$ is an incompatible edge for $(V,E)$ if and only if $$\chi(G/\{u,v\})>\chi(G).$$


**infinite chromatic topology**


Suppose that $\lambda$ is an infinite cardinal. Let $\text{pc}(\lambda)$ be the least cardinal with $\lambda^{\text{pc}(\lambda)}>\lambda$.


Proposition: $C\_{\lambda,V}^{\*}$ is a topological closure system. In the corresponding topology, the union of less than $\text{pc}(\lambda)$ many closed sets is closed, and the intersection of less than $\text{pc}(\lambda)$ many open sets is open.


If $P$ is a partition of a set $V$, then let $U\_{P}=\{\{u,v\}\mid u\neq v,u=v(P)\}$.
In the $C\_{\lambda,V}$-topology, the basic open sets are precisely the sets of the form $U\_{P}$ where $|P|\leq\lambda$.


If $\lambda=|V|$, then the $C\_{\lambda,V}$-topology is discrete.


Proposition: A non-empty subset $A\subseteq[V]^{2}$ is open in the $C\_{\lambda,V}$-topology if and only if $U\_{P}\subseteq A$ for some partition $P$ with
$|P|\leq\lambda$.


Proof: The direction $\rightarrow$ has already been established. For the direction, $\leftarrow$, suppose that $P$ is a partition of $V$ into at most $\lambda$ many sets. Then we shall show that $U\_{P}\cup\{\{p,q\}\}$ is open for each pair $p,q$ with $p\neq q$. The case where $p=q(P)$ is trivial, so assume that $p\neq q(P).$


Let $$Q=(\{\{p,q\}\}\cup\{R\setminus\{p,q\}|R\in P\})\setminus\{\emptyset\}.$$ Then
$$U\_{P}\cup\{\{p,q\}\}=U\_{P}\cup U\_{Q}.$$


Q.E.D.


Therefore, if $A\subseteq[V]^{2}$, then either $A$ is dense in the $C\_{\lambda,V}$ topology or $A$ is closed in the $C\_{\lambda,V}$ topology. Therefore, for each graph $(V,E)$, we know that $C\_{\lambda,V}(E)=[V]^{2}$ or $V\_{\lambda,V}(E)=E$. Therefore, the graph $(V,E)$ can never have an incompatible edge whenever $(V,E)$ has infinite chromatic number.


You can also argue that if $G$ has infinite chromatic number, then $G$ cannot have an incompatible edge by using the facts that that
$\chi(G/\{u,v\})\leq\chi(G)+2$ but in order for $\{u,v\}$ to be incompatible, we must have $\chi(G/\{u,v\})>\chi(G)$.


