Graphs Orientations : structures and algorithms

Orienting an undirected graph means replacing each edge by an arc with the same ends. We investigate the connectivity of the resulting directed graph. Orientations with arc-connectivity constraints are now deeply understood but very few results are known in terms of vertex-connectivity. Thomassen conjectured that sufficiently highly vertex-connected graphs have a k-vertex- connected orientation while Frank conjectured a characterization of the graphs admitting such an orientation. The results of this thesis are structures around the concepts of orientation, packing, connectivity and matroid. First, we disprove a conjecture of Recski on decomposing a graph into trees having orientations with specified indegrees. We also prove a new result on packing rooted arborescences with matroid constraints. This generalizes a fundamental result of Edmonds. Moreover, we show a new packing theorem for the bases of count matroids that induces an improvement of the only known result on Thomassen's conjecture. Secondly, we give a construction and an augmentation theorem for a family of graphs related to Frank's conjecture. To conclude, we disprove the conjecture of Frank and prove that, for every integer k >= 3, the problem of deciding whether a graph admits a k-vertex-orientation is NP-complete.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00989808
Author Durand de Gevigney, Olivier
Maintainer CCSD
Last Updated May 5, 2026, 11:31 (UTC)
Created May 5, 2026, 11:31 (UTC)
Identifier NNT: 2013GRENM027
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Optimisation Combinatoire (G-SCOP_OC) ; Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP) ; Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
creator Durand de Gevigney, Olivier
date 2013-10-18T00:00:00
harvest_object_id 5deab0ad-9b66-4190-a458-245cd3ae5f21
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-31T00:00:00
set_spec type:THESE