Deje $\Gamma$ ser simple, $3$-engañosa gráfico de tal manera que, hasta el isomorfismo, existe exactamente una acíclicos orientación de $\Gamma$ que no contiene una dirigida 3 de la ruta. (Para ser claros, cuando digo $3$-camino, me refiero a tres bordes, cuatro vértices.) Necesito que $\Gamma$ $3$- engañosa para que al menos uno de esos orientación existe (esto es un si y sólo si).
El $5$-ciclo es un ejemplo de una gráfica con esta propiedad. Hasta el isomorfismo, la única orientación que cumple este requisito es el siguiente:
Tengo un par de preguntas acerca de estos:
I. Pueden gráficos como este se caracteriza de alguna otra manera? ¿Qué es lo que hace que estos chicos sólo tienen una orientación?
Puede haber algo para el trenzado orbital cromática polinomio, se describe brevemente al final de documento. Tal vez esto de alguna manera podría ser adaptado para excluir orientaciones inducido $3-$rutas.
II. Hay más de esas otras que $C_5$, aparte de los ejemplos triviales en menos de $4$ vértices?
Originalmente pensé que estos constituyan una familia infinita de gráficos, pero para mi sorpresa, he sido incapaz de pensar en otro ejemplo. ¿La condición impide que los gráficos por encima de un cierto orden?
III. Alguien me puede ayudar a construir un algoritmo para comprobar los gráficos de este tipo en $6$ o más vértices?
Puedo usar el MAGMA y Mathematica para el idioma, o $C$ si eso es lo que quieres. (Aunque eso podría ser un poco bajo nivel para estos propósitos!)
