| dbo:abstract
|
- In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal. It is triangle-free: its girth (the length of its shortest cycle) is four. It is 4-regular: each vertex has exactly four neighbors. And its chromatic number is 4: it can be colored using four colors, but not using only three. It is, as Chvátal observes, the smallest possible 4-chromatic 4-regular triangle-free graph; the only smaller 4-chromatic triangle-free graph is the Grötzsch graph, which has 11 vertices but has maximum degree 5 and is not regular. This graph is not vertex-transitive: its automorphism group has one orbit on vertices of size 8, and one of size 4. By Brooks’ theorem, every k-regular graph (except for odd cycles and cliques) has chromatic number at most k. It was also known since that, for every k and l there exist k-chromatic graphs with girth l. In connection with these two results and several examples including the Chvátal graph,Branko Grünbaum conjectured that for every k and l there exist k-chromatic k-regular graphs with girth l. The Chvátal graph solves the case k = l = 4 of this conjecture. Grünbaum's conjecture was disproven for sufficiently large k by Johannsen (see ), who showed that the chromatic number of a triangle-free graph is O(Δ/log Δ) where Δ is the maximum vertex degree and the O introduces big O notation. However, despite this disproof, it remains of interest to find examples such as the Chvátal graph of high-girth k-chromatic k-regular graphs for small values of k. An alternative conjecture of Bruce Reed states that high-degree triangle-free graphs must have significantly smaller chromatic number than their degree, and more generally that a graph with maximum degree Δ and maximum clique size ω must have chromatic number The case ω = 2 of this conjecture follows, for sufficiently large Δ, from Johanssen's result. The Chvátal graph shows that the rounding up in Reed's conjecture is necessary, because for the Chvátal graph, (Δ + ω + 1)/2 = 7/2, a number that is less than the chromatic number but that becomes equal to the chromatic number when rounded up. The Chvátal graph is Hamiltonian, and plays a key role in a proof by that it is NP-complete to determine whether a triangle-free Hamiltonian graph is 3-colorable. The characteristic polynomial of the Chvátal graph is . The Tutte polynomial of the Chvátal graph has been computed by . The independence number of this graph is 4. (en)
- En el área matemática de la teoría de grafos, el Grafo de Chvátal es un grafo regular no dirigido de 12 vértices y 24 aristas, definido por Václav Chvátal en 1970. (es)
- 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)
- No campo matemático da teoria dos grafos, o grafo de Chvátal é um grafo não dirigido com 12 vértices e 24 arestas, descoberto por Václav Chvátal. O grafo é livre de triângulos: a sua cintura (o comprimento de seu menor ciclo) é quatro. Ele é 4-regular: cada vértice tem exatamente quatro vizinhos. O seu número cromático é quatro: pode ser colorido usando quatro cores, mas não apenas três. Ele é, como Chvátal observou, o menor possível grafo 4-cromático 4-regular livre de triângulos; o único menor grafo 4-cromático livre de triângulos é o , que tem 11 vértices mas o seu grau máximo é 5 e não é regular. (pt)
- Граф Хватала — неориентированный граф с 12 вершинами и 24 рёбрами, открытый Вацлавом Хваталом в 1970 году. (ru)
- Граф Хватала — неорієнтований граф з 12 вершинами і 24 ребрами, який 1970 року відкрив Вацлав Хватал. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6326 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
|
- Bruce Reed (en)
- Branko Grünbaum (en)
- Václav Chvátal (en)
|
| dbp:automorphisms
| |
| dbp:bookThickness
| |
| dbp:chromaticIndex
| |
| dbp:chromaticNumber
| |
| dbp:diameter
| |
| dbp:edges
| |
| dbp:first
|
- Branko (en)
- Bruce (en)
- Václav (en)
|
| dbp:girth
| |
| dbp:last
|
- Reed (en)
- Chvátal (en)
- Grünbaum (en)
|
| dbp:mode
| |
| dbp:name
| |
| dbp:namesake
| |
| dbp:properties
| |
| dbp:queueNumber
| |
| dbp:radius
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:vertices
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1970 (xsd:integer)
- 1998 (xsd:integer)
|
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En el área matemática de la teoría de grafos, el Grafo de Chvátal es un grafo regular no dirigido de 12 vértices y 24 aristas, definido por Václav Chvátal en 1970. (es)
- No campo matemático da teoria dos grafos, o grafo de Chvátal é um grafo não dirigido com 12 vértices e 24 arestas, descoberto por Václav Chvátal. O grafo é livre de triângulos: a sua cintura (o comprimento de seu menor ciclo) é quatro. Ele é 4-regular: cada vértice tem exatamente quatro vizinhos. O seu número cromático é quatro: pode ser colorido usando quatro cores, mas não apenas três. Ele é, como Chvátal observou, o menor possível grafo 4-cromático 4-regular livre de triângulos; o único menor grafo 4-cromático livre de triângulos é o , que tem 11 vértices mas o seu grau máximo é 5 e não é regular. (pt)
- Граф Хватала — неориентированный граф с 12 вершинами и 24 рёбрами, открытый Вацлавом Хваталом в 1970 году. (ru)
- Граф Хватала — неорієнтований граф з 12 вершинами і 24 ребрами, який 1970 року відкрив Вацлав Хватал. (uk)
- In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal. It is triangle-free: its girth (the length of its shortest cycle) is four. It is 4-regular: each vertex has exactly four neighbors. And its chromatic number is 4: it can be colored using four colors, but not using only three. It is, as Chvátal observes, the smallest possible 4-chromatic 4-regular triangle-free graph; the only smaller 4-chromatic triangle-free graph is the Grötzsch graph, which has 11 vertices but has maximum degree 5 and is not regular. (en)
- 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
|
- Chvátal graph (en)
- Grafo de Chvátal (es)
- Graphe de Chvátal (fr)
- Граф Хватала (ru)
- Grafo de Chvátal (pt)
- Граф Хватала (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
