| Property |
Value |
| dbo:abstract
|
- Le graphe de Chvátal est, en théorie des graphes, un graphe 4-régulier possédant 12 sommets et 24 arêtes. Il doit son nom à Václav Chvátal, qui le découvrit en 1970. Le graphe de Chvátal est hamiltonien et sans triangle. Il joue un rôle clef dans l'article de Herbert Fleischner et (en) prouvant en 2002 que déterminer si un graphe hamiltonien sans triangle est 3-colorable est un problème NP-complet. Le graphe de Chvátal sert d'illustration à la conjecture de Grünbaum qui stipule que pour tout m>1 et n>2 il existe un graphe n-régulier de nombre chromatique m et de maille au moins n. Le résultat est trivial pour n=2 et m=2,3 mais pour m>3 seuls peu de graphes illustrant la conjecture sont connus. Le graphe de Chvátal est le plus petit graphe 4-régulier sans triangle avec un nombre chromatique de 4. Le seul graphe plus petit étant sans triangle et ayant un nombre chromatique de 4 est le graphe de Grötzsch. Ce dernier a 11 sommets mais n'est pas régulier et a un sommet de degré 5. (fr)
- Le graphe de Chvátal est, en théorie des graphes, un graphe 4-régulier possédant 12 sommets et 24 arêtes. Il doit son nom à Václav Chvátal, qui le découvrit en 1970. Le graphe de Chvátal est hamiltonien et sans triangle. Il joue un rôle clef dans l'article de Herbert Fleischner et (en) prouvant en 2002 que déterminer si un graphe hamiltonien sans triangle est 3-colorable est un problème NP-complet. Le graphe de Chvátal sert d'illustration à la conjecture de Grünbaum qui stipule que pour tout m>1 et n>2 il existe un graphe n-régulier de nombre chromatique m et de maille au moins n. Le résultat est trivial pour n=2 et m=2,3 mais pour m>3 seuls peu de graphes illustrant la conjecture sont connus. Le graphe de Chvátal est le plus petit graphe 4-régulier sans triangle avec un nombre chromatique de 4. Le seul graphe plus petit étant sans triangle et ayant un nombre chromatique de 4 est le graphe de Grötzsch. Ce dernier a 11 sommets mais n'est pas régulier et a un sommet de degré 5. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5147 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:arêtes
| |
| prop-fr:automorphismes
| |
| prop-fr:diamètre
| |
| prop-fr:distribution
| |
| prop-fr:indiceChromatique
| |
| prop-fr:légende
|
- Le graphe de Chvátal (fr)
- Le graphe de Chvátal (fr)
|
| prop-fr:maille
| |
| prop-fr:nom
|
- graphe de Chvátal (fr)
- graphe de Chvátal (fr)
|
| prop-fr:nomUrl
|
- ChvatalGraph (fr)
- ChvatalGraph (fr)
|
| prop-fr:nombreChromatique
| |
| prop-fr:propriétés
| |
| prop-fr:rayon
| |
| prop-fr:sommets
| |
| prop-fr:titre
|
- Chvátal Graph (fr)
- Chvátal Graph (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- Le graphe de Chvátal est, en théorie des graphes, un graphe 4-régulier possédant 12 sommets et 24 arêtes. Il doit son nom à Václav Chvátal, qui le découvrit en 1970. Le graphe de Chvátal est hamiltonien et sans triangle. Il joue un rôle clef dans l'article de Herbert Fleischner et (en) prouvant en 2002 que déterminer si un graphe hamiltonien sans triangle est 3-colorable est un problème NP-complet. (fr)
- Le graphe de Chvátal est, en théorie des graphes, un graphe 4-régulier possédant 12 sommets et 24 arêtes. Il doit son nom à Václav Chvátal, qui le découvrit en 1970. Le graphe de Chvátal est hamiltonien et sans triangle. Il joue un rôle clef dans l'article de Herbert Fleischner et (en) prouvant en 2002 que déterminer si un graphe hamiltonien sans triangle est 3-colorable est un problème NP-complet. (fr)
|
| rdfs:label
|
- Grafo de Chvátal (es)
- Grafo de Chvátal (pt)
- Graphe de Chvátal (fr)
- Grafo de Chvátal (es)
- Grafo de Chvátal (pt)
- Graphe de Chvátal (fr)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
