| Resumé |
La partition des graphes est l'un des problèmes centraux de la théorie des graphes, issu du célèbre problème des 4 couleurs. Dans cette thèse, deux problèmes majeurs concernant la partition des graphes sont considérés : la séparation des arêtes des graphes signés et la décomposition des sommets des graphes creux. Dans la première partie de cette thèse, nous nous concentrons sur les problèmes de packing de signature des graphes signés. Un graphe signé (G, \sigma) est un graphe G équipé d'une signature \sigma qui attribue à chaque arête de G un signe (+ ou -). Le concept clé qui sépare un graphe signé d'un graphe 2-arêtes-colorées est la notion de commutation, une commutation sur un sous-ensemble X de sommets de G consiste à multiplier les signes de toutes les arêtes dans la coupe d'arête (X, V\X) par -. Un graphe signé (G, \sigma') est dit équivalent au sens de commutation (ou simplement équivalent) à (G, \sigma) s'il est obtenu par une commutation sur une coupe d'arête. Ensuite, nous définissons le nombre de packing de signature du graphe signé (G, \sigma), noté \rho(G, \sigma), comme le nombre maximal de signatures \sigma_1, \sigma_2,..., \sigma_i tel que chaque \sigma_i est équivalent à \sigma, et les ensembles E^-_{\sigma_i}, arêtes négatifs de (G, \sigma_i), sont disjoints par paires. Nous montrons qu'il est capturé par un homomorphisme spécifique. Et nous établissons une connexion avec plusieurs problèmes bien connus : par exemple, le problème des quatre couleurs, la conjecture de coloration des arêtes de Seymour. Plus précisément, nous montrons d'abord que si G est un graphe simple biparti sans K_5-mineur, alors pour toute signature \sigma, nous avons \rho(G, \sigma)\ge 4. Ensuite, nous continuons à utiliser le langage du nombre de packing et étendons la technique pour vérifier que pour tout graphe planaire signé anti-équilibré (G, \sigma) de circonférence négative d'au moins 5, nous avons \rho(G, \sigma)\ge 5. Enfin, nous étudions une généralisation du nombre de packing. Au lieu de considérer une signature et ses signatures équivalentes, nous séparons k signatures qui ne sont pas nécessairement équivalentes. Puisqu'il existe un graphe planaire de nombre de packing 1, nous recherchons des conditions suffisantes pour un graphe planaire tel que nous puissions séparer 2 ou 3 signatures. La deuxième partie de cette thèse porte sur la décomposition des sommets des graphes creux. Nous étudions d'abord la décomposition des sommets des graphes planaires de circonférence au moins 5. Il est connu que tout graphe planaire de circonférence au moins 5 peut être décomposé en deux sous-graphes induits, l'un de degré maximum au plus 3, l'autre de degré maximum au plus 5. Nous renforçons ce résultat en montrant que ces sous-graphes induits peuvent être choisis pour être des forêts. Nous travaillons ensuite sur les graphes creux avec une condition de degré moyen maximum. Plus précisément, nous utilisons la méthode du potentiel pour prouver que tout graphe G de mad(G)\le16/5 peut être un sommet décomposé en deux forêts de degré maximum au plus 1 et 4. Par conséquent, tout graphe de genre au plus 1 et de circonférence d'au moins 6 admet également une telle décomposition. |