Afficher la notice abrégée

dc.contributor.advisorSopena, Eric
dc.contributor.advisorMacgillivray, Gary
dc.contributor.authorDUFFY, Christopher
dc.date2015-08-19
dc.identifier.urihttp://www.theses.fr/2015BORD0128/abes
dc.identifier.uri
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-01227269
dc.identifier.nnt2015BORD0128
dc.description.abstractUn 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.
dc.description.abstractEnA mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j,k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j,k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)−mixed graphs) and k−edge- coloured graphs ((0,k)−mixed graphs).A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. The (j,k)−chromatic number of a (j,k)−mixed graph is the least m such that an m−colouring exists. When (j,k)=(0,1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring.In this thesis we study the (j,k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1,0)−chromatic number, more commonly called the oriented chromatic number, and the (0,k)−chromatic number.In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.
dc.language.isoen
dc.subjectGraphe
dc.subjectHomomorphisme
dc.subjectGraphe orienté
dc.subjectGraphe orientée coloration
dc.subject.enGraph
dc.subject.enHomomorphism
dc.subject.enOriented Graphs
dc.subject.enOriented colouring
dc.titleHomomorphisms of (j,k)-mixed graphs
dc.title.enHomomorphisms of (j,k)-mixed graphs
dc.typeThèses de doctorat
dc.contributor.jurypresidentThomo, Alex
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.type.institutionBordeaux
bordeaux.type.institutionUniversity of Victoria (British Columbia, Canada)
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2015BORD0128
dc.contributor.rapporteurShepherd, Bruce
dc.contributor.rapporteurHahn, Gena
dc.contributor.rapporteurPike, David
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Homomorphisms%20of%20(j,k)-mixed%20graphs&rft.atitle=Homomorphisms%20of%20(j,k)-mixed%20graphs&rft.au=DUFFY,%20Christopher&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée