Soutenance de thèse de Matthieu PETITEAU (OC) mardi 03 novembre 2026 à 9h00 à l'Institut FOURIER - Amphithéâtre Chabauty, 100 Rue des Mathématiques, 38610 Gières
Intitulée : "Orientations contraintes de graphes"
La thèse a été réalisée sous la direction de Sylvain Gravier et Isabelle Sivignon au sein de l'équipe Combinatoire et Didactique de l'Institut Fourier à Grenoble ainsi qu'au sein de la Fédération de recherche "Maths à Modeler".
L'intégralité de la présentation sera également diffusée en visioconférence au lien suivant : https://visio.numerique.gouv.fr/sca-vsgh-ikm
Les membres du jury : :
Invités :
Résumé :
Etant donné un graphe G = (V,E) et un ensemble de sommets T inclus dans V, une orientation de G est dite T-impaire si chaque sommet à un degré entrant impaire si et seulement s'il appartient à T. Dans cette thèse nous nous intéressons aux orientations acycliques T-impaire de graphe. Notamment, étant donné un graphe, quelles sont les conditions nécessaire et suffisante sur T pour qu'une telle orientation existe ?
Le chapitre 1 présente en détails ce problème, en commençant par son intérêt pour la vulgarisation scientifique. Il y est également établi, de manière plus formelle, le lien entre une situation de recherche sous forme de jeu et sa formulation en termes d’orientation de graphe.
Le chapitre 2 aborde la complexité algorithmique du problème. Nous y discutons d’abord les résultats connus, notamment l’existence d’algorithmes déterministes décidant en temps polynomial si un graphe planaire ou cubique admet une orientation acyclique V \{v}-impaire. Nous montrons ensuite qu’autoriser certaines arêtes à être pré-orientées rend le problème significativement plus difficile : dans ce cadre, décider l’existence d’une orientation acyclique T -impaire devient NP-complet, même en imposant que le graphe initial soit à la fois planaire et cubique.
Dans le chapitre 3, nous proposons trois conditions nécessaires à l’existence d’une orientation acyclique T-impaire. Ces conditions découlent principalement de la contrainte d’acyclicité, contrairement à la condition nécessaire de Chevalier, Jaeger, Payan et Xuong, qui porte sur la contrainte de parité T -impaire. Nous étudions ensuite les classes de graphes pour lesquelles ces conditions deviennent suffisantes. Nous montrons de multiples inclusions strictes entre ces classes, mettant également en évidence le rôle particulier des graphes eulériens pour ce problème.
Le chapitre 4 est le plus conséquent de ce manuscrit. Il traite l’existence d’une orientation acyclique T -impaire pour des graphes particuliers, issus de produits cartésiens de chemins et de cycles. Nous y introduisons d’abord la méthode générale qui sous-tend nos preuves : un découpage du graphe en blocs plus petits, de sorte que la construction d’orientations acycliques T -impaires sur ces blocs permette de reconstruire une orientation sur le graphe entier. Les arguments sont donc surtout techniques, moins par la diversité des outils que par le nombre de cas et de découpages à analyser. Nous obtenons finalement une caractérisation complète des couples (G, T ) tels que G admette une orientation acyclique T -impaire, lorsque G est un graphe issu de produits cartésiens de chemins et de cycles.
Le chapitre 5 traite le cas, particulièrement riche, des graphes duaux-critiques. Cette classe est centrale, car décider si un graphe admet une orientation T -impaire pour un certain T est en fait équivalent à décider si un graphe auxiliaire est dual-critique. La contribution principale de ce chapitre est une généralisation d’un résultat de Király et Kisfaludi-Bak permettant de renforcer une condition nécessaire pour qu’un graphe soit dual-critique. Nous mobilisons pour cela des résultats plus généraux de Szegedy sur les matroïdes, mettant en évidence le lien étroit entre les graphes duaux-critiques et les graphes facteur-critiques. Nous établissons ainsi un parallèle entre cette nouvelle condition nécessaire pour qu’un graphe soit dual-critique et une caractérisation connue des graphes facteur-critiques.
Enfin, dans le chapitre 6 nous établissons une généralisation de la notion d’orientation T-impaire. Cette généralisation est d’origine algébrique et s’appuie sur des opérations apparaissant dans l’algorithme de Szegedy. Nous en proposons une lecture plus graphique, avec l’espoir qu’elle aide à mieux comprendre la dualité entre les graphes duaux-critiques et les graphes facteur-critiques.
Mots-clés : graphe, orientation, acyclicité, parité, duaux-critique
ENGLISH VERSION
PhD thesis defense about "Constrained Orientations of graphs". It has been conducted as part of the Combinatoric and Didactic team of Institute Fourier as well as within the Research Federation "Math à Modeler".
Date: Tuesday, November 03rd, at 9:00 AM
Location: Institut Fourier, Amphithéâtre Chabauty, 100 Rue des Mathématiques, 38610 Gières
(https://maps.app.goo.gl/EREqD53YR6VHJ9cp7 )
Jury's Members :
Guest :
Abstract:
Given a graph G = (V,E) and a subset of vertices T in V, an orientation is said T-odd if every vertex have odd in-degree if and only if it is T. In this PhD, we are interested in acyclic T-odd orientations of graphs. In particular, given a graph, which condition would be necessary and sufficient on T so that such an orientation exists ?
Chapter 1 presents this in more detail, beginning with its value for scientific outreach. It also establishes, more formally, the link between a research situation in game form and its formulation in terms of graph orientations.
Chapter 2 deals with the algorithmic complexity of the problem. We first discuss the known results, in particular the existence of deterministic algorithms that decide in polynomial time whether a planar or cubic graph admits an acyclic V \{v}-odd orientation. We then show that allowing some edges to be pre-oriented makes the problem significantly harder: in that setting, deciding whether an acyclic T -odd orientation exists becomes NP-complete, even when the initial graph is required to be both planar and cubic.
In Chapter 3, we propose three necessary conditions for the existence of an acyclic T-odd orientation. These conditions mainly come from the acyclicity constraint, unlike the condition of Chevalier, Jaeger, Payan, and Xuong, which concerns only the T-odd parity constraint. We then study the classes of graphs for which these conditions become sufficient, highlighting the special role of Eulerian graphs in this problem.
Chapter 4 is the longest chapter in this manuscript. It studies the existence of acyclic T-odd orientations for special graphs arising from Cartesian products of paths and cycles. We first introduce the general method underlying our proofs: splitting the graph into smaller blocks, so that constructing acyclic T-odd orientations on these blocks makes it possible to rebuild an orientation on the whole graph. The arguments are therefore mainly technical, less because of the variety of tools than because of the number of cases and decompositions that must be analyzed. We ultimately obtain a complete characterization of the pairs (G, T) such that G admits an acyclic T -odd orientation, when G is a graph coming from Cartesian products of paths and cycles.
Chapter 5 deals with the particularly rich case of dual-critical graphs, i.e. graphs admitting an acyclic V \{v}-odd orientation. This class is central, because deciding whether a graph admits a T-odd orientation for some T amounts to deciding whether an auxiliary graph is dual-critical. Here we use more general results of Szegedy on matroids to extend some results of Király and Kisfaludi-Bak. We also study the dual of these results from the perspective of factor-critical graphs, in order to put them into context.
Finally, Chapter 6 proposes a generalization of the notion of T-odd orientation. This generalization originates from algebra and relies on operations appearing in Szegedy’s algorithm. We give it a more graph-theoretic interpretation, in the hope that it will help clarify the duality between graphs dual-critical and factor-critical graphs.
Keywords: graph, orientation, acyclicity, parity, dual-critical
L'intégralité de la présentation sera également diffusée en visioconférence au lien suivant : https://visio.numerique.gouv.
Les membres du jury : :
- Paul DORBEC, Professeur des universités, LIRMM, Université de Caen (Rapporteur)
- Sylvain GRAVIER, Directeur de recherche, Institut Fourier, CNRS Délégation Alpes (Directeur de thèse)
- Frédéric HAVET, Directeur de recherche, I3S, Délégation CNRS Cote d'Azur (Rapporteur)
- Aurélie LAGOUTTE, Maîtresse de conférences, G-SCOP, Université Grenoble Alpes (Examinatrice)
- Cléophée ROBIN, Maîtresse de conférences, IRIF, Université Paris Cité (Examinatrice)
- Zoltàn SZIGETI, Professeur des universités, G-SCOP, Université Grenoble Alpes (Président)
Invités :
- Isabelle SIVIGNON, Chargée de recherche, GIPSA-lab, CNRS Délégation Alpes (Co-encadrante de thèse)
Résumé :
Etant donné un graphe G = (V,E) et un ensemble de sommets T inclus dans V, une orientation de G est dite T-impaire si chaque sommet à un degré entrant impaire si et seulement s'il appartient à T. Dans cette thèse nous nous intéressons aux orientations acycliques T-impaire de graphe. Notamment, étant donné un graphe, quelles sont les conditions nécessaire et suffisante sur T pour qu'une telle orientation existe ?
Le chapitre 1 présente en détails ce problème, en commençant par son intérêt pour la vulgarisation scientifique. Il y est également établi, de manière plus formelle, le lien entre une situation de recherche sous forme de jeu et sa formulation en termes d’orientation de graphe.
Le chapitre 2 aborde la complexité algorithmique du problème. Nous y discutons d’abord les résultats connus, notamment l’existence d’algorithmes déterministes décidant en temps polynomial si un graphe planaire ou cubique admet une orientation acyclique V \{v}-impaire. Nous montrons ensuite qu’autoriser certaines arêtes à être pré-orientées rend le problème significativement plus difficile : dans ce cadre, décider l’existence d’une orientation acyclique T -impaire devient NP-complet, même en imposant que le graphe initial soit à la fois planaire et cubique.
Dans le chapitre 3, nous proposons trois conditions nécessaires à l’existence d’une orientation acyclique T-impaire. Ces conditions découlent principalement de la contrainte d’acyclicité, contrairement à la condition nécessaire de Chevalier, Jaeger, Payan et Xuong, qui porte sur la contrainte de parité T -impaire. Nous étudions ensuite les classes de graphes pour lesquelles ces conditions deviennent suffisantes. Nous montrons de multiples inclusions strictes entre ces classes, mettant également en évidence le rôle particulier des graphes eulériens pour ce problème.
Le chapitre 4 est le plus conséquent de ce manuscrit. Il traite l’existence d’une orientation acyclique T -impaire pour des graphes particuliers, issus de produits cartésiens de chemins et de cycles. Nous y introduisons d’abord la méthode générale qui sous-tend nos preuves : un découpage du graphe en blocs plus petits, de sorte que la construction d’orientations acycliques T -impaires sur ces blocs permette de reconstruire une orientation sur le graphe entier. Les arguments sont donc surtout techniques, moins par la diversité des outils que par le nombre de cas et de découpages à analyser. Nous obtenons finalement une caractérisation complète des couples (G, T ) tels que G admette une orientation acyclique T -impaire, lorsque G est un graphe issu de produits cartésiens de chemins et de cycles.
Le chapitre 5 traite le cas, particulièrement riche, des graphes duaux-critiques. Cette classe est centrale, car décider si un graphe admet une orientation T -impaire pour un certain T est en fait équivalent à décider si un graphe auxiliaire est dual-critique. La contribution principale de ce chapitre est une généralisation d’un résultat de Király et Kisfaludi-Bak permettant de renforcer une condition nécessaire pour qu’un graphe soit dual-critique. Nous mobilisons pour cela des résultats plus généraux de Szegedy sur les matroïdes, mettant en évidence le lien étroit entre les graphes duaux-critiques et les graphes facteur-critiques. Nous établissons ainsi un parallèle entre cette nouvelle condition nécessaire pour qu’un graphe soit dual-critique et une caractérisation connue des graphes facteur-critiques.
Enfin, dans le chapitre 6 nous établissons une généralisation de la notion d’orientation T-impaire. Cette généralisation est d’origine algébrique et s’appuie sur des opérations apparaissant dans l’algorithme de Szegedy. Nous en proposons une lecture plus graphique, avec l’espoir qu’elle aide à mieux comprendre la dualité entre les graphes duaux-critiques et les graphes facteur-critiques.
Mots-clés : graphe, orientation, acyclicité, parité, duaux-critique
ENGLISH VERSION
PhD thesis defense about "Constrained Orientations of graphs". It has been conducted as part of the Combinatoric and Didactic team of Institute Fourier as well as within the Research Federation "Math à Modeler".
Date: Tuesday, November 03rd, at 9:00 AM
Location: Institut Fourier, Amphithéâtre Chabauty, 100 Rue des Mathématiques, 38610 Gières
(https://maps.app.goo.gl/
Jury's Members :
- Paul DORBEC, Professor, LIRMM Université de Caen (Referee)
- Sylvain GRAVIER, Research professor, Institut Fourier, CNRS Délégation Alpes (PhD supervisor)
- Frederic HAVET, Research professor, I3S, Délégation CNRS Cote d'Azur (Referee)
- Aurélie LAGOUTTE, Associate professor, G-SCOP, Université Grenoble Alpes (Examiner)
- Cléophée ROBIN, Associate professor, IRIF, Université Paris Cité (Examiner)
- Zoltàn SZIGETI, Professor, G-SCOP, Université Grenoble Alpes (Committee chair)
Guest :
- sabelle SIVIGNON, Research assistant professor, GIPSA-lab, CNRS Délégation Alpes (PhD co-supervisor)
Abstract:
Given a graph G = (V,E) and a subset of vertices T in V, an orientation is said T-odd if every vertex have odd in-degree if and only if it is T. In this PhD, we are interested in acyclic T-odd orientations of graphs. In particular, given a graph, which condition would be necessary and sufficient on T so that such an orientation exists ?
Chapter 1 presents this in more detail, beginning with its value for scientific outreach. It also establishes, more formally, the link between a research situation in game form and its formulation in terms of graph orientations.
Chapter 2 deals with the algorithmic complexity of the problem. We first discuss the known results, in particular the existence of deterministic algorithms that decide in polynomial time whether a planar or cubic graph admits an acyclic V \{v}-odd orientation. We then show that allowing some edges to be pre-oriented makes the problem significantly harder: in that setting, deciding whether an acyclic T -odd orientation exists becomes NP-complete, even when the initial graph is required to be both planar and cubic.
In Chapter 3, we propose three necessary conditions for the existence of an acyclic T-odd orientation. These conditions mainly come from the acyclicity constraint, unlike the condition of Chevalier, Jaeger, Payan, and Xuong, which concerns only the T-odd parity constraint. We then study the classes of graphs for which these conditions become sufficient, highlighting the special role of Eulerian graphs in this problem.
Chapter 4 is the longest chapter in this manuscript. It studies the existence of acyclic T-odd orientations for special graphs arising from Cartesian products of paths and cycles. We first introduce the general method underlying our proofs: splitting the graph into smaller blocks, so that constructing acyclic T-odd orientations on these blocks makes it possible to rebuild an orientation on the whole graph. The arguments are therefore mainly technical, less because of the variety of tools than because of the number of cases and decompositions that must be analyzed. We ultimately obtain a complete characterization of the pairs (G, T) such that G admits an acyclic T -odd orientation, when G is a graph coming from Cartesian products of paths and cycles.
Chapter 5 deals with the particularly rich case of dual-critical graphs, i.e. graphs admitting an acyclic V \{v}-odd orientation. This class is central, because deciding whether a graph admits a T-odd orientation for some T amounts to deciding whether an auxiliary graph is dual-critical. Here we use more general results of Szegedy on matroids to extend some results of Király and Kisfaludi-Bak. We also study the dual of these results from the perspective of factor-critical graphs, in order to put them into context.
Finally, Chapter 6 proposes a generalization of the notion of T-odd orientation. This generalization originates from algebra and relies on operations appearing in Szegedy’s algorithm. We give it a more graph-theoretic interpretation, in the hope that it will help clarify the duality between graphs dual-critical and factor-critical graphs.
Keywords: graph, orientation, acyclicity, parity, dual-critical
Infos lieu
Institut Fourier, Amphithéâtre Chabauty, 100 Rue des Mathématiques, 38610 Gières