About: dbpedia-fr:Graphe_de_Chvátal     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : prod-dbpedia.inria.fr associated with source document(s)

AttributesValues
rdfs:label
  • Grafo de Chvátal (es)
  • Grafo de Chvátal (pt)
  • Graphe de Chvátal (fr)
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)
rdfs:seeAlso
sameAs
Wikipage page ID
Wikipage revision ID
dbo:wikiPageWikiLink
page length (characters) of wiki page
dct:subject
prop-fr:wikiPageUsesTemplate
prov:wasDerivedFrom
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/chvatal_graph.circo.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Chvatal_graph.draw.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Chvatal_graph_4COL.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Chvátal_graph.svg
prop-fr:légende
  • Le graphe de Chvátal (fr)
prop-fr:nom
  • graphe de Chvátal (fr)
prop-fr:titre
  • Chvátal Graph (fr)
prop-fr:arêtes
prop-fr:automorphismes
prop-fr:diamètre
prop-fr:distribution
prop-fr:indiceChromatique
prop-fr:maille
prop-fr:nomUrl
  • ChvatalGraph (fr)
prop-fr:nombreChromatique
prop-fr:propriétés
prop-fr:rayon
prop-fr:sommets
thumbnail
foaf:isPrimaryTopicOf
has 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)
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of
Faceted Search & Find service v1.16.111 as of Oct 19 2022


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 4 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software