Recordemos que dado un grafo \((G,r)\), un coloreo de \((G,r)\) es una asignación de colores a cada elemento de \(G\) de manera que nunca dos elementos de \(G\) que estén relacionados tengan el mismo color. En el caso en que el coloreo solo usa dos colores, le llamamos un bicoloreo de \((G,r)\). Nótese que un bicoloreo puede ser representado con un subconjunto de \(G\). Por ejemplo si el bicoloreo coloreaba a los elementos de \(G\) con dos colores, verde y rojo, podemos tomar \(R=\{g\in G:g\) es rojo\(\}\) y esto determina nuestro bicoloreo ya que \(G-R\) será justamente el conjunto de elementos verdes. O sea que matemáticamente hablando podemos dar la siguiente definición. Un bicoloreo de \((G,r)\) es un subconjunto \(R\) de \(G\) el cual cumple:
adhocprefix-adhocsufix Cualesquiera sean \(x,y\in G\) se tiene que si \((x,y)\in r\), entonces se da alguna de las siguientes condiciones:
adhocprefix(i)adhocsufix \(x\in R\) y \(y\notin R\)
adhocprefix(ii)adhocsufix \(x\notin R\) y \(y\in R\)
Esto nos inspira para dar la definición de un nuevo tipo de estructura.
Un grafo bicoloreado es una terna \((G,r,R)\), donde \((G,r)\) es un grafo y \(R\) es un bicoloreo de \((G,r)\). Algunos ejemplos:
adhocprefix-adhocsufix \((\{1,2\},\{(1,2),(2,1)\},\{1\})\) es un grafo bicoloreado
adhocprefix-adhocsufix Tomemos \[\begin{aligned} G & =\omega\\ r & =\{(x,x+1):x\in\omega\}\cup\{(x+1,x):x\in\omega\}\\ R & =\{x\in\omega:x\text{ es par}\} \end{aligned}\] Entonces \((G,r,R)\) es un grafo bicoloreado
adhocprefix-adhocsufix \((\{1,2,3,4\},\emptyset,R)\) es un grafo bicoloreado, cualesquiera sea \(R\subseteq\{1,2,3,4\}\)
Para escribir las fórmulas elementales de grafos bicoloreados, pensaremos a \(R\) como una "relación unaria" y escribiremos \(R(x)\) para expresar que \(x\in R\). Así como cuando escribimos \(r(x,y)\) pensamos "\(x\) e \(y\) están conectados", cuando escribamos \(R(x)\) pensaremos "\(x\) es rojo". Ya que no tenemos en los grafos bicoloreados operaciones ni elementos distinguidos, solo una relación unaria denotada genéricamente con el símbolo \(R\) y una relación binaria denotada genéricamente con el símbolo \(r\), los términos elementales de grafos bicoloreados serán las variables y los nombres de elementos fijos. Dejamos al lector la definición de fórmulas elementales de grafos bicoloreados.
Algunos ejemplos de fórmulas elementales de grafos bicoloreados:
adhocprefix-adhocsufix \((R(a)\wedge r(x,y))\)
adhocprefix-adhocsufix \(\exists z(r(a,z)\rightarrow R(z))\)
adhocprefix-adhocsufix \(\forall yr(a,y)\)
adhocprefix-adhocsufix \(\forall x\forall y((R(x)\wedge R(y))\rightarrow(x=y))\)
adhocprefix-adhocsufix \(\exists x\forall z(\lnot R(z)\rightarrow r(x,z))\)
adhocprefix-adhocsufix \(\forall x\forall y(r(x,y)\rightarrow(R(x)\leftrightarrow\lnot R(y)))\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z\;(((x=y)\wedge(y=z))\rightarrow(x=z))\)
Debería quedar claro que el primero de los ejemplos de fórmula elemental de grafos bicoloreados de arriba, como objeto matemático, es simplemente una palabra de longitud 13, el segundo una palabra de longitud 15, etc.