Academic literature on the topic 'Nombre chromatique de packing'

The nucleocapsid (N) protein of hantaviruses (family Bunyaviridae) is the most abundant component of the virion; it encapsidates genomic RNA segments and participates in viral genome transcription and replication, as well as in virus assembly. During RNA encapsidation, the N protein forms intermediate trimers and then oligomers via ‘head-to-head, tail-to-tail’ interactions. In previous work, using Tula hantavirus (TULV) N protein as a model, it was demonstrated that an intact coiled-coil structure of the N terminus is crucial for the oligomerization capacity of the N protein and that the hydrophobic ‘a’ residues from the second α-helix are especially important. Here, the importance of charged amino acid residues located within the coiled-coil for trimer formation and oligomerization was analysed. To predict the interacting surfaces of the monomers, the previous in silico model of TULV coiled-coils was first upgraded, taking advantage of the recently published crystal structure of the N-terminal coiled-coil of the Sin Nombre virus N protein. The results obtained using a mammalian two-hybrid assay suggested that conserved, charged amino acid residues within the coiled-coil make a substantial contribution to N protein oligomerization. This contribution probably involves (i) the formation of interacting surfaces of the N monomers (residues D35 and D38, located at the tip of the coiled-coil loop, and R63 appear particularly important) and (ii) stabilization of the coiled-coil via intramolecular ionic bridging (with E55 as a key player). It is hypothesized that the tips of the coiled-coils are the first to come into direct contact and thus to initiate tight packing of the three structures.

International audience The degree chromatic polynomial $P_m(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has m adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree. Le polynôme degré chromatique $P_m(G,k)$ d'un graphe $G$ compte le nombre de $k$-colorations dans lesquelles aucun sommet n'a m sommets adjacents de sa même couleur. On démontre la conjecture de Humpert et Martin sur les coefficients principaux du polynôme degré chromatique d'un arbre.

International audience A chromatic root is a zero of the chromatic polynomial of a graph. At a Newton Institute workshop on Combinatorics and Statistical Mechanics in 2008, two conjectures were proposed on the subject of which algebraic integers can be chromatic roots, known as the ``$α +n$ conjecture'' and the ``$nα$ conjecture''. These say, respectively, that given any algebraic integer α there is a natural number $n$ such that $α +n$ is a chromatic root, and that any positive integer multiple of a chromatic root is also a chromatic root. By computing the chromatic polynomials of two large families of graphs, we prove the $α +n$ conjecture for quadratic and cubic integers, and show that the set of chromatic roots satisfying the nα conjecture is dense in the complex plane. Une racine chromatique est un zéro du polynôme chromatique d'un graphe. A un atelier au Newton Institute sur la combinatoire et la mécanique statistique en 2008, deux conjectures ont été proposées dont le sujet des entiers algébriques peut être racines chromatiques, connus sous le nom ``la conjecture $α + n$'' et ``la conjecture $n α$ ''. Les conjectures veulent dire, respectivement, que pour chaque entier algébrique $α$ il y a un nombre entier naturel $n$, tel que $α + n$ est une racine chromatique, et que chaque multiple entier positif d'une racine chromatique est aussi une racine chromatique . En calculant les polynômes chromatiques de deux grandes familles de graphes, on prouve la conjecture $α + n$ pour les entiers quadratiques et cubiques, et montre que l'ensemble des racines chromatiques qui confirme la conjecture $nα$ est dense dans le plan complexe.

International audience Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Björner and de Longueville have shown that its box complex is homotopy equivalent to a sphere, $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. The dihedral group $D_{2m}$ acts canonically on $SG_{n,k}$. We study the $D_{2m}$ action on $\mathrm{Hom}(K_2,SG_{n,k})$ and define a corresponding orthogonal action on $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. We establish a close equivariant relationship between the graphs $SG_{n,k}$ and Borsuk graphs of the $k$-sphere and use this together with calculations in the $\mathbb{Z}_2$-cohomology ring of $D_{2m}$ to tell which stable Kneser graphs are test graphs in the sense of Babson and Kozlov. The graphs $SG_{2s,4}$ are test graphs, i.e. for every graph $H$ and $r \geq 0$ such that $\mathrm{Hom}(SG_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi (H)$ is at least $r+6$. On the other hand, if $k \notin \{0,1,2,4,8\}$ and $n \geq N(k)$ then $SG_{n,k}$ is not a homotopy test graph, i.e. there are a graph $G$ and an $r \geq 1$ such that $\mathrm{Hom}(SG_{n,k}, G)$ is $(r-1)$-connected and $\chi (G) < r+k+2$. The latter result also depends on a new necessary criterion for being a test graph, which involves the automorphism group of the graph. Schrijver a défini le graphe de Kneser stable $SG_{n,k}$, avec $n \geq 1$ et $k \geq 0$. Le graphe $SG_{n,k}$ est un graphe critique (par rapport aux sommets) de nombre chromatique $k+2$, dont les sommets correspondent à certains sous-ensembles d'un ensemble de cardinalité $m=2n+k$. Björner et de Longueville ont démontré que son complexe de boîtes et la sphère sont homotopiquement équivalents, c'est-à-dire $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. Le groupe diédral $D_{2m}$ agit sur $SG_{n,k}$ canoniquement. Nous étudions l'action de $D_{2m}$ sur $\mathrm{Hom}(K_2,SG_{n,k})$ et nous définissons une action orthogonale correspondante sur $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. Par ailleurs, nous fournissons une relation équivariante étroite entre les graphes $SG_{n,k}$ et les graphes de Borsuk de la sphère de dimension $k$. Utilisant cette relation et certains calculs dans l'anneau de cohomologie de $D_{2m}$ sur $\mathbb{Z}_2$, nous décrivons quels graphes de Kneser stables sont des graphes de tests selon la notion de Babson et Kozlov. Les graphes $SG_{2s,4}$ sont des graphes de tests, c'est-à-dire que pour tout $H$ et $r \geq 0$ tels que $\mathrm{Hom}(SG_{2s,4},H)$ est $(r-1)$-connexe, le nombre chromatique $\chi (H)$ est au moins $r+6$. D'autre part, si $k \notin \{0,1,2,4,8\}$ et $n \geq N(k)$, alors $SG_{n,k}$ n'est pas un graphe de tests d'homologie: il existe un graphe $G$ et un entier $r \geq 1$ tels que $\mathrm{Hom}(SG_{n,k}, G)$ est $(r-1)$-connexe et $\chi (G) < r+k+2$. Ce dernier résultat dépend d'un nouveau critère nécessaire pour être un graphe de tests, qui implique le groupe d'automorphismes du graphe.

Cette thèse de doctorat est divisée en deux parties principales: La partie I explore l'existence de chemins orientés dans les digraphes, cherchant à établir un lien entre le nombre chromatique d'un digraphe et l'existence de chemins orientés spécifiques en tant que sous-digraphes. Les digraphes contenus dans n'importe quel digraphe n-chromatique sont appelés n-universels. Nous examinons deux conjectures : la conjecture de Burr, qui affirme que chaque arbre orienté d'ordre n est (2n-2)-universel, et la conjecture d'El Sahili, qui déclare que chaque chemin orienté d'ordre n est n-universel. Pour les chemins orientés en général, la meilleure borne est donnée par Burr, à savoir que chaque chemin orienté d'ordre n est (n - 1)²-universel.Notre objectif est d'étudier des chemins à trois blocs. Pour atteindre nos objectifs, nous nous appuyons fortement sur des concepts fondamentaux, y compris l'induction sur l'ordre d'un digraphe donné, les forêts finales, les techniques de nivellement et les méthodes de décomposition stratégique de digraphes. Un chemin comportant trois blocs est désigné par P(k1, k2, k3). Pour le chemin P(k,1,l), nous avons confirmé la conjecture d'El Sahili dans les digraphes Hamiltoniens. En se basant sur ce résultat pour les digraphes Hamiltoniens, nous avons confirmé la conjecture d'El Sahili pour une classe plus générale de digraphes, ceux qui incluent un chemin dirigé hamiltonien. Nous introduisons une technique novatrice : une décomposition du digraphe en sous-digraphes résultant d'une série d'opérations basées sur le fameux théorème de Roy, qui garantit l'existence d'un chemin orienté dirigé d'ordre n dans tout digraphe n-chromatique. Cette technique s'est avérée cruciale pour établir de nouvelles bornes linéaires pour le nombre chromatique de digraphes qui ne comportent pas de chemin orienté avec trois blocs. En effet, en utilisant cette technique, nous avons prouvé que le chemin P(k,1,l) satisfait la conjecture de Burr. De plus, pour n'importe quel chemin à trois blocs, P(k,l,r), nous avons établi une borne linéaire pour le nombre chromatique qui améliore toutes les bornes précédemment atteintes. Dans la partie II, nous étudions le problème de la coloration de packing dans les graphes. Étant donnée une séquence non décroissante S = (s1, s2, . . . , sk) d'entiers positifs, une S-coloration (de packing) d'un graphe G est une partition de l'ensemble des sommets de G en k sous-ensembles {V1, V2, . . . , Vk} tels que pour chaque 1 ≤ i ≤ k, la distance entre deux sommets distincts u et v dans Vi est d'au moins si + 1. Notre attention est centrée sur une conjecture intrigante proposée par Brešar et al., qui affirme que l'arête subdivision de n'importe quel graphe subcubique admet une (1,2,3,4,5)-coloration de packing. Notre objectif est de confirmer cette conjecture pour des classes spécifiques de graphes subcubiques et de traiter les questions non résolues soulevées dans ce domaine. Une observation de Gastineau et Togni indique que si un graphe G est (1, 1, 2, 2)-colorable, alors son graphe subdivisé S(G) est (1,2,3,4,5)-colorable, et donc il satisfait la conjecture. En nous basant sur cette observation et afin de prouver la véracité de la conjecture pour la classe des graphes de Halin cubiques, nous avons étudié leur S-coloration de packing visant à prouver qu'ils admettent une coloration en (1, 1, 2, 2). Nous avons prouvé que tout graphe de Halin cubique est (1, 1, 2, 3)-colorable, et donc (1, 1, 2, 2)-colorable, et ainsi nous confirmons la conjecture pour cette classe. De plus, Gastineau et Togni, après avoir prouvé que chaque graphe subcubique est (1, 2, 2, 2, 2, 2, 2)-colorable, ont posé un problème ouvert sur le fait de savoir si chaque graphe subcubique est (1, 2, 2, 2, 2, 2)-colorable. Nous répondons affirmativement à cette question dans la classe particulière sur laquelle nous avons travaillé : nous avons prouvé que les graphes d'Halin cubiques sont (1, 2, 2, 2, 2, 2)-colorables
This PhD thesis is divided into two principal parts: Part I delves into the existenceof oriented paths in digraphs, aiming to establish a connection between a digraph'schromatic number and the existence of specific oriented paths within it as subdigraphs. Digraphs contained in any n-chromatic digraph are called n-universal. We consider two conjectures: Burr's conjecture, which states that every oriented tree of order n is (2n-2)-universal, and El Sahili's conjeture which states that every oriented path of order n is n-universal. For oriented paths in general, the best bound is given by Burr, that is every oriented path of order n is (n − 1)^2-universal. Our objective is to study the existence of an integer k such that any digraph with a chromatic number k, contains a copy of a given oriented path with three blocks as its subdigraph. To achieve our goals, we rely significantly on fundamental concepts, including, induction on the order of a given digraph, final forests, leveling techniques, and strategic digraph decomposition methods. A path P (k1, k2, k3) is an oriented path consisting of k1 forward arcs, followed by k2 backward arcs, and then by k3 forward arcs. For the path P(k,1,l), we have confirmed El Sahili's conjecture in Hamiltonian digraphs. More clearly, we have established the existence of any path P (k, 1, l) of order n in any n-chromatic Hamiltonian digraph. And depending on this result concerning Hamiltonian digraphs, we proved the correctness of El Sahili's conjecture on a more general class of digraphs which is digraphs containing a Hamiltonian directed path. We introduce a new technique which is represented by a decomposition of the digraph into subdigraphs defined by a series of successive operations applied to the digraph relying on the famous theorem of Roy which establishes the existence of a directed path of order n in any n-chromatic digraph. This technique has proven to be instrumental in establishing new linear bounds for the chromatic number of digraphs that lack an oriented path with three blocks. In deed, using this technique, we proved that the path P(k,1,l) satisfies Burr's conjecture.Moreover, for any path with three blocks, P(k,l,r) we establish a linear bound for the chromatic number which improves all the previously reached bounds. In Part II we study the problem of S-packing coloring in graphs. Given a non-decreasing sequence S = (s1, s2, . . . , sk) of positive integers, an S-packing coloring of a graph G is a partition of the vertex set of G into k subsets{V1, V2, . . . , Vk} such that for each 1 ≤ i ≤ k, the distance between any two dis-tinct vertices u and v in Vi is at least si + 1. Our focus is centered on an intriguing conjecture proposed by Brešar et al., which states that packing chromatic number of the subdivision of any subcubic graph is at most 5. Our desired aim is to provide a confirmation of this conjecture for specific classes of subcubic graphs, and to address the unresolved issues raised within this subject matter. An observation for Gastineau and Togni states that if a graph G is (1, 1, 2, 2)-packing colorable, then the chromatic number of its subdivision graph S(G) is at most 5, and hence it satisfies the conjecture. Depending on this observation, and in order to prove the correctness of the conjecture for the class of cubic Halin graphs, we studied its S-packing coloring aiming to prove that it admits a (1, 1, 2, 2)- packing coloring. We proved that a cubic Halin graph is (1, 1, 2, 3)-packing colorable, then it is (1, 1, 2, 2)-packing colorable, and so we confirm the conjecture for this class. Moreover, Gastineau and Togni, after proving that every subcubic graph is (1, 2, 2, 2, 2, 2, 2)-packing colorbale, have posed an open problem on whether every subcubic graph is (1, 2, 2, 2, 2, 2)-packing colorable. We answer this question in affirmative in the particular class we worked on; we proved that cubic Halin graphs are (1, 2, 2, 2, 2, 2)-packing colorable

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance
Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets
A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints
Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs

Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres : cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1. ) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1
Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres : cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1. ) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1

Cette thèse concerne la théorie structurelle des graphes. Elle contient un certain nombre de résultats, aussi bien algorithmiques que structurels, sur les graphes ne contenant pas certains graphes en tant que sous graphes ou sous-graphes induits. Les graphes exclus consistent en des variations autour des configurations de Truemper. Celles-ci peuvent être vues comme des généalisations du cycle
This thesis is concerned with structural graph theory. It contains several results, algorithmics and structural, on classes of graphs defined by forbidding induced subgraphs. Graphs that are excluded are variations around the so-called "Truemper configurations". These last might be seen as generalization of the cycle

We apply the semidefinite programming method to obtain a new upper bound on the cardinality of codes made of subspaces of a linear vector space over a finite field. Such codes are of interest in network coding.Next, with the same method, we prove an upper bound on the cardinality of sets avoiding one distance in the Johnson space, which is essentially Schrijver semidefinite program. This bound is used to improve existing results on the measurable chromatic number of the Euclidean space.We build a new hierarchy of semidefinite programs whose optimal values give upper bounds on the independence number of a graph. This hierarchy is based on matrices arising from simplicial complexes. We show some properties that our hierarchy shares with other classical ones. As an example, we show its application to the problem of determining the independence number of Paley graphs.

La thèse porte sur les deux thèmes des Jeux combinatoires et de la théorie des graphes. Elle est divisée en deux parties.1) Le jeu de Domination et ses variantes: Il s'agit d'un jeu combinatoire qui consiste à marquer les sommets d'un graphe de telle sorte qu'un sommet marqué n'ait aucun voisin marqué. Le joueur marquant le dernier sommet est déclaré gagnant. Le calcul des stratégies gagnantes étant NP-difficile pour un graphe quelconque, nous avons étudié des familles particulières de graphes comme les chemins, les scies ou les chenilles. Pour ces familles on peut savoir en temps polynomial si un graphe est perdant. Nous avons également étudié 28 variantes du jeu de domination, dont les 12 variantes définies par J. Conway sur un jeu combinatoire quelconque. 2) Le nombre chromatique ludique des arbres: Ce paramètre est calculé à partir d'un jeu de coloration où Alice et Bob colorient alternativement et proprement un sommet d'un graphe G avec l'une des k couleurs. L'objectif d'Alice est de colorier complètement le graphe alors que Bob doit l'en empêcher. Nous nous sommes intéressés au jeu avec 3 couleurs sur un arbre T. Nous souhaitons déterminer les arbres ayant un nombre chromatique ludique 3, soit ceux pour lesquels Alice a une stratégie gagnante avec 3 couleurs. Ce problème semblant difficile à résoudre sur les arbres, nous avons résolu des sous-familles: les 1-chenilles puis les chenilles sans trous
Part 1: Domination Game and its variantsDomination game is a combinatorial game that consists in marking vertices of a graph so that a marked vertex has no marked neighbors. The first player unable to mark a vertex loses the game.Since the computing of winning strategies is an NP-hard problem for any graphs, we examine some specific families of graphs such as complete k-partite graphs, paths or saws. For these families, we establish the set of losing elements. For other families, such as caterpillars, we prove that exists a polynomial algorithm for the computation of outcome and winning strategies. No polynomial algorithm has been found to date for more general families, such as trees.We also study 28 variants of Domination game, including the 12 variants defined by J. Conway for any combinatorial game. Using game functions, we find the set of losing paths for 10 of these 12 variants. We also investigate 16 variants called diameter, for instance when rules require to play on the component that has the largest diameter.Part 2: The game chromatic number of treesThis parameter is computed from a coloring game: Alice and Bob alternatively color the vertices of a graph G, using one of the k colors in the color set. Alice has to achieve the coloring of the entire graph whereas Bob has to prevent this. Faigle and al. proved that the game chromatic number of a tree is at most 4. We undertake characterization of trees with a game chromatic number of 3. Since this problem seems difficult for general trees, we focus on sub-families: 1-caterpillars and caterpillars without holes.For these families we provide the characterization and also compute winning strategies for Alice and Bob. In order to do so, we are led to define a new notion, the bitype, that for a partially-colored graph G associates two letters indicating who has a winning strategy respectively on G and G with an isolated vertex. Bitypes allow us to demonstrate several properties, in particular to compute the game chromatic number of a graph from the bitypes of its connected components

Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1.) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1.