• Décomposition de tournois en classes acycliques, Jean-François Culus and Bertrand Jouve, Proceeding of SFC2004. Bordeaux, France (2004). [Article]
Ce tout premier article étudie une première généralisation de la coloration aux graphes orientés en la positionnant par rapport à la littérature dans le domaine. On étudie ici la décomposition d’un graphe orienté en classes acycliques avec contrainte d’uni-direction entre les couleurs. On s’intéresse plus spécifiquement aux tournois indécomposables (les classes acycliques sont les singletons) et montrons qu’ils sont denses parmi l’ensemble des tournois lorsque la taille du graphe tend vers l’infini. Enfin, on s’intéresse à la notion de tournoi sommet-critique indécomposable (ie la suppression de tout sommet conduit à un graphe décomposable) et caractérisons la structure de ceux-ci comme étant composés de tournois circulants.

• Tournois sans intervalles acycliques, Jean-François Culus and Bertrand Jouve, Compte rendu de l’Académie Scientifique Paris, Ser I341 (2005) [Article]
Cet article est la version longue du précédent, avec les différentes démonstrations. On introduit la décomposition étudiée au moyen de la terminologie des intervalles : tout sommet extérieur à un intervalle est soit dominé soit dominant tous les sommets de l’intervalle.

• Polynôme chromatique mixte et interprétation des coefficients , Jean-François Culus, Roadef 2006, Lille, France (2006). [Article]
On s’intéresse ici à une autre décomposition de graphe orientée, dans laquelle les classes sont comme dans la coloration classique des sous-ensembles stables avec contrainte d’uni-direction entre deux couleurs (ainsi, coloré un sommet ne dépend pas uniquement des couleurs de ses voisins mais aussi des relations entre les couleurs elles-mêmes). On s’intéresse ici à interpréter des coefficients du polynôme chromatique orienté à la manière de Stanley pour ceux du polynôme chromatique classique (interprétation comme nombre d’orientations acircuitiques du graphe). Cette interprétation nécessite l’introduction d’un graphe mixte construit à partir du graphe orienté, et d’une généralisation de la notion de coloration orienté aux graphes mixtes. Les outils ici utilisés sont d’algèbre et de combinatoire.

• Oriented coloring: complexity and approximation, Jean-François Culus and Marc Demange, SOFSEM 2006 Theory and Practice of Computer Science, LNCS 3831 (2006) [Article]
Dans cet article, nous démontrons la NP-complétude du problème de coloration orientée pour k=4 même sur des instances très spécifiques et mettons en évidence qu’il est polynomial sur l’ensemble des graphes orientés multipartis complets. Au moyen d’une réduction du problème de sous-ensemble stable maximum, nous montrons que le problème de minimisation du nombre chromatique orienté n’est pas approximable à rapport constant en différentiel (à moins que NP n’égale P). Enfin, sous une condition un peu moins restrictive (ZPP≠P), ce problème n’est pas approximable avec un rapport d’approximation différentiel de l’ordre de n-1.

• Inverse booking problem: inverse chromatic number problem in interval graphs, Yerim Chung, Jean-François Culus and Marc Demange, Lecture Notes in Computer Sciences 4921, Walcom: Algorithms and Computations, Dhaka (Bangladesh): Elsevier, (2008) [Article]
Il s’agit ici d’étudier, sous l’angle de l’approximation polynômiale, un problème de recherche opérationnelle (problème de planification). Ayant un nombre fixé de chambres, quelles incitations peut-on demander aux clients pour modifier leurs réservations de quelques jours afin de maximiser au final le taux d’occupation des chambres. Formellement, ce problème est le problème inverse du nombre chromatique dans les graphes d’intervalles. Ce problème est connu pour être n-approximable. Au moyen d’une réduction, nous prouvons qu’il n’est pas O(n1-)-approximable (à moins que P=NP) et qu’il est donc NP-difficile au sens fort.

• Convex circuit free coloration of an oriented graph, Jean-François Culus and Bertrand Jouve, European Journal of Combinatorics (2009) [Article]
Cet article est une version approfondie de la note CRAS publiée en 2005. On s’intéresse donc la décomposition d’un graphe orienté en classes convexe (un sous-ensemble de sommet étant convexe si tout 2-chemins ayant ses extrémités dans cette partie est totalement contenue dans celle-ci) sans circuit (CCF-coloration). On s’intéresse à la complexité du problème de décision associé : le graphe orienté donné admet-il une k-CCF-coloration, pour k fixé ? Nous montrons que ce problème est NP-complet dès que k=4 (polynômial si k≤3) par réduction de 3-SAT. Ce problème est néanmoins polynomial pour la classe des tournois. La densité des tournois CCF-indécomposables dans l’ensemble des tournois est établie quand le nombre de sommet tends vers l’infini. Enfin, une caractérisation des tournois CCF-indécomposable critique (ie. Le retrait d’un sommet laisse un tournoi CCF-décomposable) est donnée comme étant des tournois constitués à partir de tournois circulants. Cet article propose plus de liens avec des autres travaux du domaine.

• On inverse Chromatic Number problems, Yerim Chung, Jean-François Culus and Marc Demange, Electronic Notes in Discrete Mathematics (2010)

• Inverse chromatic number problems in interval and permutation graphs, Yerim Chung, Jean-François Culus and Marc Demange, European Journal of Operational Research, (2015) [Article]
Poursuivant l’article de WALCOM 2008, on s’intéresse au problème inverse de coloration à la fois dans les graphes d’intervalle ainsi que dans les graphes de permutation. Nous le relions déjà à d’autres problèmes classiques de recherche opérationnelle, tels des problèmes de planification ou d’assignation de tâches en reprenant leur formalisme et symbolique. Nous obtenons de nouveaux résultats de complexité et proposons des classes polynomiales en exhibant un algorithme de résolution dans ce cas.

• About some robustiness and complexity properties of G-graphs networks, Jean-François Culus, Marc Demange, Ruxandra Marinescu-Ghemeci and Cerasela Tanasescu, Discrete Applied Mathematics (2015) [Article]
Cet article s’intéresse à l’étude de la structure de G-graphes, qui sont des graphes générés à partir d’un groupe (G,.) (un peu à l’image des graphes de Cayley). Si S est un sous ensemble de G, et on considère le graphe d’intersection des classes par rapport aux sous-groupes engendrés par les éléments de S. On s’intéresse à la robustesse de ces graphes (par délétion de sommet ou d’arête) ainsi qu’à la complexité du problème de reconnaissance de ces graphes. On exhibe alors une classe de G-graphe optimalement connectés (dont particulièrement robustes, ce qui peut être intéressant pour modèle d’un réseau) et fournissons un algorithme polynomial de reconnaissance de ces graphes dans le cas où le groupe G est abélien.

• 2CSPs all are approximable within some constant differential factor, Sophie Toulouse and Jean-François Culus, ISCO 2018, à paraître [Article]
On s’intéresse ici à l’approximation en temps polynomial du problème de satisfaction de contraintes k-CSP sur un alphabet de taille q. Ce problème est facilement approximable avec le critère de l’approximation classique (ratio nombre de clauses satisfaites sur nombre de clauses satisfaites à l’optimum). Des résultats plus équivoques sont connu selon la mesure de gain (ratio de l’écart à la valeur moyenne par l’écart entre l’optimum et la valeur moyenne) ; en particulier, il semble difficile de faire mieux que la valeur moyenne (obtenue via la méthode des probabilités conditionnelles). Mais très peu de résultats sont connus quant à son approximation différentielle (ratio de l’écart à la pire solution par l’écart entre la meilleur et la pire solution). Dans cet article, nous générons, à partir de tableaux particuliers, un ensemble de solutions sur lequel nous obtenons un nouveau rapport d’approximation différentiel. Dans ce cas particulier du 2-CSP, nous obtenons un rapport d’approximation différentiel constant.