6.4 Grafos bicoloreados

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:

1. - Cualesquiera sean $x,y\in G$ se tiene que si $(x,y)\in r$, entonces se da alguna de las siguientes condiciones:

   1. $x\in R$ y $y\notin R$

   2. $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:

1. - $\left(\right\{1,2\},\{(1,2),(2,1)\},\{1\left\}\right)$ es un grafo bicoloreado

2. - Tomemos $$\begin{array}{cc}G& =\omega \\ r& =\left\{\right(x,x+1):x\in \omega \}\cup \left\{\right(x+1,x):x\in \omega \}\\ R& =\{x\in \omega :x\text{es par}\}\end{array}$$ Entonces $(G,r,R)$ es un grafo bicoloreado

3. - $\left(\right\{1,2,3,4\},\varnothing ,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\left(x\right)$ para expresar que $x\in R$. Asi como cuando escribimos $r(x,y)$ pensamos "$x$ e $y$ estan conectados", cuando escribamos $R\left(x\right)$ 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:

1. - $\left(R\right(a)\wedge r(x,y\left)\right)$

2. - $\exists z\left(r\right(a,z)\to R(z\left)\right)$

3. - $\forall yr(a,y)$

4. - $\forall x\forall y\left(\right(R\left(x\right)\wedge R\left(y\right))\to (x=y\left)\right)$

5. - $\exists x\forall z\left(\neg R\right(z)\to r(x,z\left)\right)$

6. - $\forall x\forall y\left(r\right(x,y)\to (R\left(x\right)\leftrightarrow \neg R\left(y\right)\left)\right)$

7. - $\forall x\forall y\forall z\left(\right((x=y)\wedge (y=z))\to (x=z\left)\right)$

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.