"American Mathematical Society"@fr . "April 1979"@fr . "Ku\u010Dera"@fr . . . "Daniel"@fr . "Markossian"@fr . "Herbert Wilf"@fr . . "408312"^^ . "709826"^^ . "A min-max theorem for graphs with application to graph coloring"@fr . "R."@fr . "Stanley M."@fr . "182"^^ . "34710"^^ . "The greedy coloring is a bad probabilistic algorithm"@fr . "Vishwanathan"@fr . "10.1007"^^ . "Lud\u011Bk"@fr . "New methods to color the vertices of a graph"@fr . "513"^^ . "65"^^ . . "Topics in Perfect Graphs"@fr . . "Smallest-last ordering and clustering and graph coloring algorithms"@fr . . "G. S."@fr . "Sritharan"@fr . "85"^^ . "Fernando Magno Quint\u00E3o"@fr . . "Matula"@fr . "Graph Colorings"@fr . . "Sequential coloring versus Welsh\u2013Powell bound"@fr . "Kubale"@fr . "Mitchem"@fr . "Maciej M."@fr . "Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandst\u00E4dt et Takao Nishizeki"@fr . "David W."@fr . "An on-line graph coloring algorithm with sublinear performance ratio"@fr . . "109"^^ . "On various algorithms for estimating the chromatic number of a graph"@fr . "Bruce Reed et Cl\u00E1udia L. Sales"@fr . "Encyclopedia of Mathematics and its Applications"@fr . "1130323"^^ . "Simmons"@fr . "Michael Saks"@fr . . "Christen"@fr . "36"^^ . "B. A."@fr . . . "3780"^^ . "33"^^ . "The smallest hard-to-color graph for algorithm DSATUR"@fr . . "CMS Books in Mathematics"@fr . "21"^^ . "An extremal problem in recursive combinatorics"@fr . "11"^^ . "Winnipeg, Manitoba"@fr . "The ordered chromatic number of planar maps"@fr . . "1"^^ . "graphe de Meyniel"@fr . "Dominic Welsh"@fr . "5"^^ . "Jens"@fr . "1"^^ . "Middendorf"@fr . "Saks"@fr . "Lueker"@fr . . "Thore"@fr . "1001404"^^ . "7"^^ . "25"^^ . "4"^^ . . "5"^^ . "\u0416\u0430\u0434\u0456\u0431\u043D\u0435 \u0440\u043E\u0437\u0444\u0430\u0440\u0431\u043E\u0432\u0443\u0432\u0430\u043D\u043D\u044F"@uk . . "On coloring unit disk graphs"@fr . "Robert E."@fr . "12"^^ . "13"^^ . "1049253"^^ . . . "10"^^ . "48"^^ . "9781420011074"^^ . "11"^^ . "20"^^ . "Tarjan"@fr . "21"^^ . "22"^^ . "34"^^ . "SIAM 1968 National Meeting"@fr . "Powell"@fr . "Kierstead"@fr . "19"^^ . . "Poletto"@fr . "January 9, 2006"@fr . "30"^^ . "396344"^^ . "McDiarmid"@fr . "Frank"@fr . "27"^^ . "Springer"@fr . . "2798"^^ . "59"^^ . "Dans l'\u00E9tude des probl\u00E8mes de coloration de graphes en math\u00E9matiques et en informatique, une coloration gloutonne ou coloration s\u00E9quentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en s\u00E9quence et attribue \u00E0 chaque sommet la premi\u00E8re couleur disponible. Les colorations gloutonnes peuvent \u00EAtre obtenues en temps lin\u00E9aire, mais elles n'utilisent en g\u00E9n\u00E9ral pas le nombre minimum possible de couleurs. Diff\u00E9rents choix pour la suite des sommets produisent g\u00E9n\u00E9ralement des colorations diff\u00E9rentes du graphe donn\u00E9. Une grande partie de l'\u00E9tude des colorations gloutonnes porte donc sur la fa\u00E7on de trouver un bon ordre. Il existe toujours un ordre qui produit une coloration optimale, et m\u00EAme si l'on trouve ais\u00E9ment pour de nombreuses classes particuli\u00E8res de graphes, ils sont difficiles \u00E0 trouver en g\u00E9n\u00E9ral. Les strat\u00E9gies couramment utilis\u00E9es pour l'ordre des sommets impliquent de choisir les sommets de degr\u00E9 \u00E9lev\u00E9 avant les sommets de degr\u00E9 inf\u00E9rieur, ou de choisir des sommets avec moins de couleurs disponibles de pr\u00E9f\u00E9rence aux sommets qui sont moins contraints. Des variantes de coloration gloutonne consistent \u00E0 choisir les couleurs par un algorithme online, donc sans connaissance de la structure de la partie non color\u00E9e du graphe, ou de choisir d'autres couleurs que la premi\u00E8re couleur disponible afin de r\u00E9duire le nombre total de couleurs. Des algorithmes de coloration gloutonne ont \u00E9t\u00E9 appliqu\u00E9s \u00E0 des probl\u00E8mes d'ordonnancement et d'allocation de registres, \u00E0 l'analyse de jeux combinatoires et aux preuves d'autres r\u00E9sultats math\u00E9matiques, notamment le th\u00E9or\u00E8me de Brooks sur la relation entre coloration et degr\u00E9. D'autres concepts de th\u00E9orie des graphes d\u00E9riv\u00E9s des colorations gloutonnes incluent le nombre de Grundy d'un graphe (le plus grand nombre de couleurs que l'on peut trouver dans une coloration gloutonne), et les graphes bien color\u00E9s, qui sont les graphes pour lesquels toutes les colorations gloutonnes utilisent le m\u00EAme nombre de couleurs."@fr . "Leibniz International Proceedings in Informatics"@fr . . . "53"^^ . "63"^^ . "N. Bansal, E. Merelli et J. Worrell"@fr . "49"^^ . "W. R."@fr . . "10.1137"^^ . "Wilf"@fr . "Coloring Meyniel graphs in linear time"@fr . "10.1006"^^ . "681909"^^ . "Pereira"@fr . "On the coloration of perfect graphs"@fr . "Amsterdam"@fr . . "10.1016"^^ . "William T. Trotter"@fr . "Electronic Notes in Discrete Mathematics"@fr . "Algorithmic aspects of vertex elimination on graphs"@fr . "Zaker"@fr . "Wei\u00DFenfels"@fr . "Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing"@fr . "Triangular prism.png"@fr . "437376"^^ . "3166"^^ . "Bruce Reed"@fr . "67"^^ . . . . "Massimiliano"@fr . . "74"^^ . "75"^^ . "80"^^ . "Nivasch"@fr . "Sarkar"@fr . . "481"^^ . "well-colored graph"@fr . . "726050"^^ . . "Gabriel"@fr . "Some perfect coloring properties of graphs"@fr . "156"^^ . "Maffray"@fr . "539075"^^ . "Husfeldt"@fr . "L. L."@fr . . "Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing"@fr . "CRC Press"@fr . . . . . "Results on the Grundy chromatic number of graphs"@fr . . "989136"^^ . . "Random Structures & Algorithms"@fr . . "1247988"^^ . "Amin Saberi"@fr . "hal-archives ouvertes"@fr . "W. T."@fr . "L\u00E1szl\u00F3 Lov\u00E1sz"@fr . . "895"^^ . "S. T."@fr . . "417"^^ . "Trotter"@fr . "Gasparian"@fr . "Sundar"@fr . "David S. Johnson"@fr . "L."@fr . "Topics in Chromatic Graph Theory"@fr . "Gustavus J."@fr . "Schloss Dagstuhl"@fr . "236"^^ . "Algorithmica"@fr . "Lecture Notes in Computer Science"@fr . "Reed"@fr . "Three short proofs in graph theory"@fr . "Sandy"@fr . "Lov\u00E1sz"@fr . . "Series B"@fr . . "L\u00E9v\u00EAque"@fr . "327"^^ . "198"^^ . . . "Claude Berge et Va\u0161ek Chv\u00E1tal"@fr . . "Erd\u0151s\u2013R\u00E9nyi model"@fr . . "Thu\u1EADt to\u00E1n t\u00F4 m\u00E0u tham lam"@vi . . . "Chapman & Hall/CRC Computer and Information Science Series"@fr . "Colin"@fr . "John"@fr . . "1611517"^^ . "Graph colouring algorithms"@fr . . "10.1145"^^ . "Square antiprism.png"@fr . "graphes bien color\u00E9s"@fr . . . "Register allocation via coloring of chordal graphs"@fr . "Providence, Rhode Island"@fr . "14275665"^^ . "Ho\u00E0ng"@fr . "1187207"^^ . "Le prisme triangulaire et l'anti-prisme carr\u00E9 sont des graphes pour lesquels la coloration gloutonne avec l'ordre d\u00E9g\u00E9n\u00E9r\u00E9 donne un nombre de couleurs plus grand que le nombre optimal."@fr . "Dans l'\u00E9tude des probl\u00E8mes de coloration de graphes en math\u00E9matiques et en informatique, une coloration gloutonne ou coloration s\u00E9quentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en s\u00E9quence et attribue \u00E0 chaque sommet la premi\u00E8re couleur disponible. Les colorations gloutonnes peuvent \u00EAtre obtenues en temps lin\u00E9aire, mais elles n'utilisent en g\u00E9n\u00E9ral pas le nombre minimum possible de couleurs."@fr . "Coloration gloutonne"@fr . "Claude A."@fr . . "Manuszewski"@fr . "269"^^ . "Robert E. Tarjan"@fr . . "M. E."@fr . "266"^^ . . "2264378"^^ . . "Chapter 28. Perfect Graphs"@fr . "Hare"@fr . . "277"^^ . "Beck"@fr . "10.423"^^ . "10.1002"^^ . "1385380"^^ . "1505.06"^^ . "M."@fr . "Erd\u0151s"@fr . "Hedetniemi"@fr . "Coloring inductive graphs on-line"@fr . "277"^^ . "Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2\u20135, 2005, Proceedings"@fr . "Manouchehr"@fr . "Johnson"@fr . . . "SIAM Review"@fr . . . . . "Meyniel graph"@fr . "Worst case behavior of graph coloring algorithms"@fr . "Irani"@fr . . . . . . "319"^^ . "Linear scan register allocation"@fr . . "David S."@fr . "Donald J."@fr . "Perfectly orderable graphs"@fr . "Rose"@fr . . "Kwangkeun Yi"@fr . "315"^^ . . "K."@fr . "On the complexity of recognizing perfectly orderable graphs"@fr . . . . "Journal of Algorithms"@fr . "Laskar"@fr . . "Algorithmic theory of random graphs"@fr . "Lowell W. Beineke et Robin J. Wilson"@fr . "707"^^ . . "Kosowski"@fr . "An inequality for the chromatic number of a graph"@fr . "1489033"^^ . "10.109"^^ . "Welsh"@fr . "Gerhard"@fr . . "306"^^ . "1830607"^^ . . "889347"^^ . "An upper bound for the chromatic number of a graph and its application to timetabling problems"@fr . "Piwakowski"@fr . "10.1093"^^ . . "1974"^^ . "1975"^^ . "Classical coloring of graphs"@fr . "Congressus Numerantium"@fr . "https://hal.archives-ouvertes.fr/file/index/docid/30179/filename/ColMeyniel.pdf| date = October 2005"@fr . . "Cambridge University Press"@fr . . . "1968"^^ . . "1982"^^ . . "1983"^^ . "1981"^^ . "352"^^ . "1979"^^ . . "1976"^^ . "George Szekeres"@fr . "X"@fr . "Elsevier"@fr . . "190037492"^^ . "1967"^^ . "Sys\u0142o"@fr . "Szekeres"@fr . "Pfeiffer"@fr . "Stumpf"@fr . "Utilitas Math."@fr . "Fr\u00E9d\u00E9ric"@fr . "2021"^^ . "graphe bien color\u00E9"@fr . . "The greedy algorithm is not optimal for on-line edge coloring"@fr . "Handbook of Graph Theory, Combinatorial Optimization, and Algorithms"@fr . "Vivek"@fr . "1952983"^^ . "Benjamin"@fr . "Matthias"@fr . "Gr\u00E4f"@fr . "George"@fr . "The Sprague\u2013Grundy function of the game Euclid"@fr . "M. B."@fr . . . "Congressus Numerantium"@fr . . "P."@fr . . . "https://users.renyi.hu/~p_erdos/1987-18.pdf| volume = 11"@fr . "On the equality of the Grundy and ochromatic numbers of a graph"@fr . "Selkow"@fr . "Michael P. H."@fr . "Chinh T."@fr . "Springer-Verlag"@fr . "Dominic J. A."@fr . "Erratum : MCColor is not optimal on Meyniel graphs"@fr . "657"^^ . "1574"^^ . . "\u03B2-perfect graphs"@fr . . "389644"^^ . . "S. E."@fr . . . "David Wajc"@fr . . "4"^^ . . "2273147"^^ . "674"^^ . "5"^^ . "2"^^ . "3"^^ . "1"^^ . . "Annals of Discrete Mathematics"@fr . . "Janczewski"@fr . "2016"^^ . "Va\u0161ek Chv\u00E1tal"@fr . . "Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II"@fr . . "cs/0405059"@fr . . "Herbert S."@fr . "21"^^ . "2006"^^ . "400"^^ . "Br\u00E9laz"@fr . "2004"^^ . "251"^^ . "2005"^^ . "2003"^^ . "3380176"^^ . "Recent Advances in Algorithms and Combinatorics"@fr . "graphes de Meyniel"@fr . "2001"^^ . "Krzysztof"@fr . "241"^^ . "2015"^^ . "Paul Erd\u0151s"@fr . "mod\u00E8le d'Erd\u0151s-R\u00E9nyi"@fr . "September 1999"@fr . "143"^^ . . "1990"^^ . "1991"^^ . "North-Holland"@fr . "1989"^^ . "Contemporary Mathematics"@fr . "1987"^^ . "1984"^^ . "1998"^^ . . "H. A."@fr . "1996"^^ . "Palsberg"@fr . "Albert"@fr . "1997"^^ . "1994"^^ . "157"^^ . "Renu C. Laskar"@fr . "1992"^^ . "Randomized online graph coloring"@fr . "Adrian"@fr . "0"^^ . "Marek Kubale"@fr . "151"^^ . . "2076987"^^ . .