Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque j<i.Dans cette exposé, nous présentons des résultats connus à propos de la S-coloration de packing. Nous apportons de nouveaux résultats à propos de la S-coloration de packing, pour des classes de graphes telles que les chemins, les cycles et les arbres. Nous étudions en détail la complexité du problème de complexité associé à la S-coloration de packing, noté S -COL. Pour certaines instances de S -COL, nous caractérisons des dichotomies entre problèmes NP-complets et problèmes résolubles en tempspolynomial. Nous nous intéressons aux différentes grilles infinies, les grilles hexagonale, carrée, triangulaire et du roi et nous déterminons des propriétés de subdivisions d’un i-packing en plusieurs j-packings, avec j>i. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5. / Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each j<i.In this presentation, we present results about S-packing coloring. We prove new results about the S-coloring of graphs including paths, cycles and trees. We study the complexity problem associated to the S-packing coloring, this problem is denoted S-COL. For some instances of S-COL, we characterize dichotomy between NP-complete problems and problems solved by a polynomial time algorithm. We study also different lattices, the hexagonal, square, triangular and king lattices. We determine properties on the subdivision of an i-packing in several j-packings, for j>i. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5.

Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles