Functional graphs

Un graphe G est dit graphe fonctionnel s'il existe deux applications f et g de V(G) dans un ensemble F telles que xy est une arête de G si et seulement si f(x)=g(y) ou g(x)=f(y). Chvátal et Ebenegger ont prouvé que le problème de reconnaissance des graphes fonctionnels est NP-complet. En utilisant le théorème de compacité, nous prouvons que si G est un graphe infini tel que tout sous-graphe fini de G est fonctionnel, alors G est fonctionnel. Nous donnons une preuve élémentaire de ce fait dans le cas dénombrable. Dans le cas fini, nous prouvons que pour n suffisamment grand, tout graphe sans cycle d'ordre plus petit que n et contenant au plus 3n−7 sommets est un graphe fonctionnel. Il sera montré à l'aide d'un exemple que 3n−7 est la meilleure borne possible. Pour citer cet article : A. El Sahili, C. R. Acad. Sci. Paris, Ser. I 341 (2005).