Recordemos que dado un grafo \((G,r)\), un coloreo de \((G,r)\) es una asignacion de colores a cada elemento de \(G\) de manera que nunca dos elementos de \(G\) que esten relacionados tengan el mismo color. En el caso en que el coloreo solo usa dos colores, le llamamos un bicoloreo de \((G,r)\). Notese 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\) sera justamente el conjunto de elemenos verdes. O sea que matematicamente hablando podemos dar la siguiente definicion. 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:
\(x\in R\) y \(y\notin R\)
\(x\notin R\) y \(y\in R\)
Esto nos inspira para dar la definicion 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, cualesquera sea \(R\subseteq\{1,2,3,4\}\)
Para escribir las formulas elementales de grafos bicoloreados, pensaremos a \(R\) como una "relacion unaria" y escribiremos \(R(x)\) para expresar que \(x\in R\). Asi como cuando escribimos \(r(x,y)\) pensamos "\(x\) e \(y\) estan conectados", cuando escribamos \(R(x)\) pensaremos "\(x\) es rojo". Dejamos al lector la definicion de terminos elementales de grafos bicoloreados y de formulas elementales de grafos bicoloreados.
Algunos ejemplos de formulas 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))\)
Deberia quedar claro que el primero de los ejemplos de formula elemental de grafos bicoloreados de arriba, como objeto matematico, es simplemente una palabra de longitud 13.