Aunque es "bien sabido" que un gráfico paralelo en serie (simple) tiene un número cromático como máximo de 3, parece que no puedo encontrar una prueba de esta afirmación en ningún sitio.
¿Alguien sabe cómo probar esta afirmación?
Puede estar relacionado con el hecho de que los gráficos paralelos en serie son libres de K4 menores.
Todo gráfico serie-paralelo (GSP) puede ser coloreado con un máximo de $3$ colores de tal manera que su origen y su destino se coloreen de forma diferente (una coloración P). Esto es claramente cierto para el caso base, una sola arista.
Supongamos que tenemos dos SPG de color P; el origen y el sumidero del primero están coloreados con colores $a$ y $b$ , el de la segunda $c$ y $d$ respectivamente. Al permutar los colores
Como todos los SPG están formados por composiciones en serie y en paralelo a partir de la arista única, esto demuestra por inducción que todos los SPG tienen una coloración P, es decir, un $3$ -Coloración.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
