Recordemos que dado un grafo , un coloreo de es una asignacion de colores a cada elemento de de manera que nunca dos elementos de que esten relacionados tengan el mismo color. En el caso en que el coloreo solo usa dos colores, le llamamos un bicoloreo de . Notese que un bicoloreo puede ser representado con un subconjunto de . Por ejemplo si el bicoloreo coloreaba a los elementos de con dos colores, verde y rojo, podemos tomar es rojo y esto determina nuestro bicoloreo ya que sera justamente el conjunto de elemenos verdes. O sea que matematicamente hablando podemos dar la siguiente definicion. Un bicoloreo de es un subconjunto de el cual cumple:
- Cualesquiera sean se tiene que si , entonces se da alguna de las siguientes condiciones:
y
y
Esto nos inspira para dar la definicion de un nuevo tipo de estructura.
Un grafo bicoloreado es una terna , donde es un grafo y es un bicoloreo de . Algunos ejemplos:
- es un grafo bicoloreado
- Tomemos Entonces es un grafo bicoloreado
- es un grafo bicoloreado, cualesquera sea
Para escribir las formulas elementales de grafos bicoloreados, pensaremos a como una "relacion unaria" y escribiremos para expresar que . Asi como cuando escribimos pensamos " e estan conectados", cuando escribamos pensaremos " 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:
-
-
-
-
-
-
-
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.