Property |
Value |
dbo:abstract
|
- En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. Les graphes qui ont un nombre de Hadwiger au plus égal à quatre ont été caractérisés par Wagner en 1937. Les graphes qui ont un nombre de Hadwiger fini borné sont peu denses et ont aussi un petit nombre chromatique. La détermination du nombre de Hadwiger d'un graphe est NP-difficile mais traitable à paramètre fixe. (fr)
- En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. Les graphes qui ont un nombre de Hadwiger au plus égal à quatre ont été caractérisés par Wagner en 1937. Les graphes qui ont un nombre de Hadwiger fini borné sont peu denses et ont aussi un petit nombre chromatique. La détermination du nombre de Hadwiger d'un graphe est NP-difficile mais traitable à paramètre fixe. (fr)
|
dbo:thumbnail
| |
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 11314 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:année
|
- 1937 (xsd:integer)
- 1943 (xsd:integer)
- 1976 (xsd:integer)
- 1980 (xsd:integer)
- 1984 (xsd:integer)
- 1991 (xsd:integer)
- 1993 (xsd:integer)
- 2001 (xsd:integer)
- 2007 (xsd:integer)
- 2009 (xsd:integer)
- 2010 (xsd:integer)
|
prop-fr:arxiv
|
- 807.000700 (xsd:double)
- 910.007900 (xsd:double)
- math/9301216 (fr)
|
prop-fr:doi
|
- 10.100600 (xsd:double)
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.109000 (xsd:double)
- 10.715500 (xsd:double)
|
prop-fr:fr
|
- poursuite-évasion (fr)
- refuge (fr)
- graphe apex (fr)
- poursuite-évasion (fr)
- refuge (fr)
- graphe apex (fr)
|
prop-fr:journal
| |
prop-fr:lienAuteur
|
- Béla Bollobás (fr)
- Paul Erdős (fr)
- David Eppstein (fr)
- Robin Thomas (fr)
- Noga Alon (fr)
- Neil Robertson (fr)
- Paul Seymour (fr)
- Rudolf Halin (fr)
- Hugo Hadwiger (fr)
- Klaus Wagner (fr)
- Oum Sang-il (fr)
- Béla Bollobás (fr)
- Paul Erdős (fr)
- David Eppstein (fr)
- Robin Thomas (fr)
- Noga Alon (fr)
- Neil Robertson (fr)
- Paul Seymour (fr)
- Rudolf Halin (fr)
- Hugo Hadwiger (fr)
- Klaus Wagner (fr)
- Oum Sang-il (fr)
|
prop-fr:mr
|
- 444522 (xsd:integer)
- 1141945 (xsd:integer)
- 1164063 (xsd:integer)
|
prop-fr:nom
|
- Robertson (fr)
- Seymour (fr)
- Thomas (fr)
- Wagner (fr)
- Alon (fr)
- Erdős (fr)
- Eppstein (fr)
- Halin (fr)
- Fomin (fr)
- Bollobás (fr)
- Catlin (fr)
- Hadwiger (fr)
- Thomason (fr)
- Thilikos (fr)
- Oum (fr)
- Wahlen (fr)
- Kostochka (fr)
- Lingas (fr)
- Robertson (fr)
- Seymour (fr)
- Thomas (fr)
- Wagner (fr)
- Alon (fr)
- Erdős (fr)
- Eppstein (fr)
- Halin (fr)
- Fomin (fr)
- Bollobás (fr)
- Catlin (fr)
- Hadwiger (fr)
- Thomason (fr)
- Thilikos (fr)
- Oum (fr)
- Wahlen (fr)
- Kostochka (fr)
- Lingas (fr)
|
prop-fr:numéro
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
- 4 (xsd:integer)
- 7 (xsd:integer)
|
prop-fr:pages
|
- 84 (xsd:integer)
- 133 (xsd:integer)
- 149 (xsd:integer)
- 171 (xsd:integer)
- 195 (xsd:integer)
- 197 (xsd:integer)
- 279 (xsd:integer)
- 303 (xsd:integer)
- 307 (xsd:integer)
- 318 (xsd:integer)
- 570 (xsd:integer)
- 1617 (xsd:integer)
|
prop-fr:prénom
|
- Andrew (fr)
- Paul (fr)
- David (fr)
- Robin (fr)
- Martin (fr)
- Rudolf (fr)
- Hugo (fr)
- Klaus (fr)
- Andrzej (fr)
- Neil (fr)
- Paul A. (fr)
- Noga (fr)
- Béla (fr)
- Fedor V. (fr)
- Dimitrios M. (fr)
- Sang-il (fr)
- Alexandr V. (fr)
- Andrew (fr)
- Paul (fr)
- David (fr)
- Robin (fr)
- Martin (fr)
- Rudolf (fr)
- Hugo (fr)
- Klaus (fr)
- Andrzej (fr)
- Neil (fr)
- Paul A. (fr)
- Noga (fr)
- Béla (fr)
- Fedor V. (fr)
- Dimitrios M. (fr)
- Sang-il (fr)
- Alexandr V. (fr)
|
prop-fr:series
|
- Series B (fr)
- Series B (fr)
|
prop-fr:texte
|
- refuges (fr)
- graphes apex (fr)
- refuges (fr)
- graphes apex (fr)
|
prop-fr:titre
|
- Excluding infinite minors (fr)
- Hadwiger's conjecture for K6-free graphs (fr)
- Linkless embeddings of graphs in 3-space (fr)
- Über eine Klassifikation der Streckenkomplexe (fr)
- Über eine Eigenschaft der ebenen Komplexe (fr)
- Approximating the maximum clique minor and some subgraph homeomorphism problems (fr)
- Finding large clique minors is hard (fr)
- Hadwiger's conjecture is true for almost every graph (fr)
- Rank-width and tree-width of H-minor-free graphs (fr)
- S-functions for graphs (fr)
- The extremal function for complete minors (fr)
- Lower bound of the Hadwiger number of graphs by their average degree (fr)
- Excluding infinite minors (fr)
- Hadwiger's conjecture for K6-free graphs (fr)
- Linkless embeddings of graphs in 3-space (fr)
- Über eine Klassifikation der Streckenkomplexe (fr)
- Über eine Eigenschaft der ebenen Komplexe (fr)
- Approximating the maximum clique minor and some subgraph homeomorphism problems (fr)
- Finding large clique minors is hard (fr)
- Hadwiger's conjecture is true for almost every graph (fr)
- Rank-width and tree-width of H-minor-free graphs (fr)
- S-functions for graphs (fr)
- The extremal function for complete minors (fr)
- Lower bound of the Hadwiger number of graphs by their average degree (fr)
|
prop-fr:trad
|
- Haven (fr)
- Pursuit-evasion (fr)
- Apex graph (fr)
- Haven (fr)
- Pursuit-evasion (fr)
- Apex graph (fr)
|
prop-fr:url
| |
prop-fr:volume
|
- 1 (xsd:integer)
- 4 (xsd:integer)
- 8 (xsd:integer)
- 13 (xsd:integer)
- 28 (xsd:integer)
- 31 (xsd:integer)
- 81 (xsd:integer)
- 88 (xsd:integer)
- 95 (xsd:integer)
- 114 (xsd:integer)
- 374 (xsd:integer)
|
prop-fr:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. (fr)
- En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. (fr)
|
rdfs:label
|
- Nombre de Hadwiger (fr)
- Число Хадвигера (ru)
- Nombre de Hadwiger (fr)
- Число Хадвигера (ru)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |