This HTML5 document contains 464 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n9http://g.co/kg/m/
n19https://drops.dagstuhl.de/opus/volltexte/2021/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n14https://hal.archives-ouvertes.fr/file/index/docid/30179/filename/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-cshttp://cs.dbpedia.org/resource/
n6http://fr.dbpedia.org/resource/Modèle:
n24http://fr.dbpedia.org/resource/Fichier:
n22https://users.renyi.hu/~p_erdos/
n4http://fr.dbpedia.org/resource/Modèle:Traduction/
wikipedia-frhttp://fr.wikipedia.org/wiki/
n16http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n25http://ma-graph.org/entity/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n28https://www.python.org/doc/essays/graphs/
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Coloration_gloutonne
rdf:type
owl:Thing wikidata:Q8366 dbo:Algorithm
rdfs:label
Жадібне розфарбовування Thuật toán tô màu tham lam Coloration gloutonne
rdfs:comment
Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible. Les colorations gloutonnes peuvent être obtenues en temps linéaire, mais elles n'utilisent en général pas le nombre minimum possible de couleurs.
owl:sameAs
dbpedia-cs:First_fit_algoritmus_barvení_grafu n9:05b62q1 dbpedia-vi:Thuật_toán_tô_màu_tham_lam dbpedia-fa:رنگ_آمیزی_آزمند dbpedia-uk:Жадібне_розфарбовування dbpedia-ru:Жадная_раскраска n25:38767284 dbpedia-it:Colorazione_golosa wikidata:Q5601715 dbr:Greedy_coloring
dbo:wikiPageID
14275665
dbo:wikiPageRevisionID
190037492
dbo:wikiPageWikiLink
dbpedia-fr:Dégénérescence_(théorie_des_graphes) dbpedia-fr:Théorème_de_Sprague-Grundy dbpedia-fr:The_Computer_Journal dbpedia-fr:Sous-graphe dbpedia-fr:Graphe_roue dbpedia-fr:Prisme_triangulaire dbpedia-fr:Graphe_à_distance_héréditaire dbpedia-fr:Communications_of_the_ACM dbpedia-fr:Algorithme_d'approximation dbpedia-fr:Antiprisme_carré dbpedia-fr:SIAM_Journal_on_Computing dbpedia-fr:Compilateur dbpedia-fr:Voisinage_(théorie_des_graphes) dbpedia-fr:Algorithmica dbpedia-fr:Python_(langage) dbpedia-fr:Parcours_de_graphe dbpedia-fr:Jeu_impartial dbpedia-fr:Algorithme_récursif dbpedia-fr:Algorithme_glouton dbpedia-fr:Algorithme_online dbpedia-fr:Stable_(théorie_des_graphes) dbpedia-fr:Théorème_de_Brooks dbpedia-fr:Journal_of_Combinatorial_Theory dbpedia-fr:Graphe_aléatoire dbpedia-fr:Graphe_acyclique dbpedia-fr:Allocation_de_registres dbpedia-fr:Graphe_(mathématiques_discrètes) dbpedia-fr:Informatique dbpedia-fr:Degré_(théorie_des_graphes) dbpedia-fr:Problème_NP-complet dbpedia-fr:Jeux_de_Nim n24:Greedy_colourings.svg dbpedia-fr:Coloration_de_graphe dbpedia-fr:Graphe_complet dbpedia-fr:Graphe_complémentaire dbpedia-fr:Graphe_biparti dbpedia-fr:Graphe_cactus dbpedia-fr:Journal_of_Graph_Theory dbpedia-fr:Graphe_d'intervalles dbpedia-fr:Graphe_cordal dbpedia-fr:ACM_Transactions_on_Programming_Languages_and_Systems dbpedia-fr:Graphe_couronne dbpedia-fr:DSATUR dbpedia-fr:Mathématiques dbpedia-fr:Graphe_des_cycles dbpedia-fr:Avec_grande_probabilité dbpedia-fr:Journal_of_the_ACM dbpedia-fr:Graphe_de_disques dbpedia-fr:Graphe_de_comparabilité dbpedia-fr:Complexité_en_temps dbpedia-fr:Ensembles_disjoints category-fr:Coloration_d'un_graphe dbpedia-fr:Alan_Frieze dbpedia-fr:Cographe dbpedia-fr:Clique_(théorie_des_graphes) dbpedia-fr:Graphe_parfait dbpedia-fr:NP-difficile dbpedia-fr:Cardinalité_(mathématiques) dbpedia-fr:Sommet_(théorie_des_graphes) dbpedia-fr:Théorie_des_jeux_combinatoires dbpedia-fr:Discrete_Mathematics dbpedia-fr:Algorithme
dbo:wikiPageExternalLink
n14:ColMeyniel.pdf%7C n22:1987-18.pdf%7C n19:14178 n28:
dbo:wikiPageLength
34710
dct:subject
category-fr:Coloration_d'un_graphe
prop-fr:wikiPageUsesTemplate
n4:référence n6:Références n6:Portail n6:Multiple_image n6:Mvar n6:Lien n6:Harvsp n6:Formule n6:Chapitre n6:Article n6:Math n6:Loupe n6:Sfnp
prov:wasDerivedFrom
wikipedia-fr:Coloration_gloutonne?oldid=190037492&ns=0
foaf:depiction
n16:Greedy_colourings.svg n16:Square_antiprism.png n16:Triangular_prism.png
prop-fr:année
1974 1975 1968 1982 1983 1981 1979 1976 1967 2016 2006 2004 2005 2003 2001 2015 1990 1991 1989 1987 1984 1998 1996 1997 1994 1992
prop-fr:arxiv
1505.06 cs/0405059
prop-fr:auteur
Amin Saberi dbpedia-fr:Alan_Frieze David Wajc Vašek Chvátal
prop-fr:auteurOuvrage
Kwangkeun Yi Marek Kubale
prop-fr:collection
Encyclopedia of Mathematics and its Applications CMS Books in Mathematics Leibniz International Proceedings in Informatics Lecture Notes in Computer Science Chapman & Hall/CRC Computer and Information Science Series Annals of Discrete Mathematics Contemporary Mathematics
prop-fr:date
April 1979 January 9, 2006 2021 September 1999
prop-fr:doi
10.1007 10.1137 10.1006 10.1016 10.1145 10.423 10.1002 10.109 10.1093
prop-fr:footer
Le prisme triangulaire et l'anti-prisme carré sont des graphes pour lesquels la coloration gloutonne avec l'ordre dégénéré donne un nombre de couleurs plus grand que le nombre optimal.
prop-fr:fr
graphe de Meyniel graphe bien coloré modèle d'Erdős-Rényi
prop-fr:image
Triangular prism.png Square antiprism.png
prop-fr:isbn
9781420011074 0
prop-fr:journal
dbpedia-fr:SIAM_Journal_on_Computing dbpedia-fr:The_Computer_Journal Random Structures & Algorithms dbpedia-fr:Journal_of_Combinatorial_Theory Algorithmica dbpedia-fr:Algorithmica SIAM Review dbpedia-fr:Journal_of_Graph_Theory Journal of Algorithms Congressus Numerantium dbpedia-fr:Discrete_Mathematics dbpedia-fr:ACM_Transactions_on_Programming_Languages_and_Systems dbpedia-fr:Journal_of_the_ACM dbpedia-fr:Communications_of_the_ACM
prop-fr:lienAuteur
Herbert Wilf Michael Saks Dominic Welsh William T. Trotter Bruce Reed László Lovász David S. Johnson Robert E. Tarjan George Szekeres Paul Erdős Renu C. Laskar
prop-fr:lieu
Winnipeg, Manitoba Amsterdam Providence, Rhode Island
prop-fr:nom
Kučera Markossian Vishwanathan Sritharan Matula Kubale Mitchem Simmons Christen Middendorf Saks Lueker Tarjan Powell Kierstead Poletto McDiarmid Wilf Pereira Zaker Weißenfels Nivasch Sarkar Maffray Husfeldt Trotter Gasparian Reed Lovász Lévêque Hoàng Manuszewski Hare Beck Erdős Hedetniemi Johnson Irani Rose Laskar Kosowski Welsh Piwakowski Sysło Szekeres Pfeiffer Stumpf Gräf Selkow Janczewski Brélaz Palsberg
prop-fr:numéro
4 5 2 3 1 21
prop-fr:pages
182 513 85 5 1 25 2798 59 53 49 3166 481 895 417 327 269 266 277 319 657 674 251 241 143 157 151
prop-fr:passage
65 109 1 63 277 315 707
prop-fr:prénom
Daniel R. Stanley M. Luděk G. S. Fernando Magno Quintão Maciej M. David W. B. A. Jens Thore Robert E. Frank W. R. Massimiliano Gabriel L. L. W. T. S. T. Sundar L. Gustavus J. Sandy Colin John Claude A. M. E. M. Manouchehr David S. Donald J. K. Gerhard Frédéric Vivek Benjamin Matthias George M. B. P. Michael P. H. Chinh T. Dominic J. A. S. E. Herbert S. Krzysztof H. A. Albert Adrian
prop-fr:périodique
Electronic Notes in Discrete Mathematics hal-archives ouvertes Congressus Numerantium
prop-fr:texte
graphes bien colorés graphes de Meyniel
prop-fr:titre
A min-max theorem for graphs with application to graph coloring The greedy coloring is a bad probabilistic algorithm New methods to color the vertices of a graph Smallest-last ordering and clustering and graph coloring algorithms Sequential coloring versus Welsh–Powell bound An on-line graph coloring algorithm with sublinear performance ratio On various algorithms for estimating the chromatic number of a graph The smallest hard-to-color graph for algorithm DSATUR An extremal problem in recursive combinatorics The ordered chromatic number of planar maps On coloring unit disk graphs Coloring Meyniel graphs in linear time On the coloration of perfect graphs Algorithmic aspects of vertex elimination on graphs Some perfect coloring properties of graphs Results on the Grundy chromatic number of graphs Three short proofs in graph theory Graph colouring algorithms Register allocation via coloring of chordal graphs Chapter 28. Perfect Graphs Coloring inductive graphs on-line Worst case behavior of graph coloring algorithms Linear scan register allocation Perfectly orderable graphs On the complexity of recognizing perfectly orderable graphs Algorithmic theory of random graphs An inequality for the chromatic number of a graph An upper bound for the chromatic number of a graph and its application to timetabling problems Classical coloring of graphs The greedy algorithm is not optimal for on-line edge coloring The Sprague–Grundy function of the game Euclid On the equality of the Grundy and ochromatic numbers of a graph Erratum : MCColor is not optimal on Meyniel graphs β-perfect graphs Randomized online graph coloring
prop-fr:titreOuvrage
Topics in Perfect Graphs Graph Colorings 48 Topics in Chromatic Graph Theory Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2–5, 2005, Proceedings Handbook of Graph Theory, Combinatorial Optimization, and Algorithms Recent Advances in Algorithms and Combinatorics
prop-fr:titreVolume
7 Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing
prop-fr:totalWidth
400
prop-fr:trad
well-colored graph Erdős–Rényi model Meyniel graph
prop-fr:url
n19:14178 https://hal.archives-ouvertes.fr/file/index/docid/30179/filename/ColMeyniel.pdf| date = October 2005 https://users.renyi.hu/~p_erdos/1987-18.pdf| volume = 11
prop-fr:volume
36 33 4 5 12 13 10 11 20 21 22 19 30 27 67 74 75 80 236 306 X
prop-fr:éditeur
American Mathematical Society Springer CRC Press Schloss Dagstuhl Cambridge University Press Elsevier Utilitas Math. Springer-Verlag North-Holland
prop-fr:auteursOuvrage
Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandstädt et Takao Nishizeki Bruce Reed et Cláudia L. Sales N. Bansal, E. Merelli et J. Worrell Claude Berge et Vašek Chvátal Lowell W. Beineke et Robin J. Wilson
prop-fr:numéroDansCollection
3780 21 11 34 156 198 352
prop-fr:mr
408312 709826 1130323 1001404 1049253 396344 681909 437376 726050 539075 989136 1247988 1611517 1187207 2264378 1385380 1489033 1830607 889347 1952983 389644 2273147 3380176 2076987
prop-fr:hal
1574
prop-fr:series
Series B
dbo:thumbnail
n16:Greedy_colourings.svg?width=300
prop-fr:department
SIAM 1968 National Meeting Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II
foaf:isPrimaryTopicOf
wikipedia-fr:Coloration_gloutonne
dbo:abstract
Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible. Les colorations gloutonnes peuvent être obtenues en temps linéaire, mais elles n'utilisent en général pas le nombre minimum possible de couleurs. Différents choix pour la suite des sommets produisent généralement des colorations différentes du graphe donné. Une grande partie de l'étude des colorations gloutonnes porte donc sur la façon de trouver un bon ordre. Il existe toujours un ordre qui produit une coloration optimale, et même si l'on trouve aisément pour de nombreuses classes particulières de graphes, ils sont difficiles à trouver en général. Les stratégies couramment utilisées pour l'ordre des sommets impliquent de choisir les sommets de degré élevé avant les sommets de degré inférieur, ou de choisir des sommets avec moins de couleurs disponibles de préférence aux sommets qui sont moins contraints. Des variantes de coloration gloutonne consistent à choisir les couleurs par un algorithme online, donc sans connaissance de la structure de la partie non colorée du graphe, ou de choisir d'autres couleurs que la première couleur disponible afin de réduire le nombre total de couleurs. Des algorithmes de coloration gloutonne ont été appliqués à des problèmes d'ordonnancement et d'allocation de registres, à l'analyse de jeux combinatoires et aux preuves d'autres résultats mathématiques, notamment le théorème de Brooks sur la relation entre coloration et degré. D'autres concepts de théorie des graphes dérivés 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és, qui sont les graphes pour lesquels toutes les colorations gloutonnes utilisent le même nombre de couleurs.