Homomorphisms of (j,k)-mixed graphs

Abstract

Un graphe mixte est un graphe simple tel que un sous-ensemble des arêtes a une orientation. Pour entiers non négatifs j et k, un graphe mixte-(j,k) est un graphe mixte avec j types des arcs and k types des arêtes. La famille de graphes mixte-(j,k) contient graphes simple, (graphes mixte−(0,1)), graphes orienté (graphes mixte−(1,0)) and graphe coloré arête −k (graphes mixte−(0,k)).Un homomorphisme est un application sommet entre graphes mixte−(j,k) que tel les types des arêtes sont conservés et les types des arcs et leurs directions sont conservés. Le nombre chromatique−(j,k) d’un graphe mixte−(j,k) est le moins entier m tel qu’il existe un homomorphisme à une cible avec m sommets. Quand on observe le cas de (j,k) = (0,1), on peut déterminer ces définitions correspondent à les définitions usuel pour les graphes.Dans ce mémoire on etude le nombre chromatique−(j,k) et des paramètres similaires pour diverses familles des graphes. Aussi on etude les coloration incidence pour graphes and digraphs. On utilise systèmes de représentants distincts et donne une nouvelle caractérisation du nombre chromatique incidence. On define le nombre chromatique incidence orienté et trouves un connexion entre le nombre chromatique incidence orienté et le nombre chromatic du graphe sous-jacent.