Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Chvátal_graph> ?p ?o. }
Showing items 1 to 47 of
47
with 100 items per page.
- Chvátal_graph 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 (1970).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: the automorphisms 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 Erdős (1959) 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 (1970) 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 Reed 1998), 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 (1998) 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 numberThe 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 Fleischner & Sabidussi (2002) 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 Björklund et al. (2008).The independence number of this graph is 4.".
- Chvátal_graph thumbnail Chvatal_graph.draw.svg?width=300.
- Chvátal_graph wikiPageID "22258988".
- Chvátal_graph wikiPageRevisionID "569357236".
- Chvátal_graph authorlink "Branko Grünbaum".
- Chvátal_graph authorlink "Bruce Reed".
- Chvátal_graph authorlink "Václav Chvátal".
- Chvátal_graph automorphisms "8".
- Chvátal_graph chromaticIndex "4".
- Chvátal_graph chromaticNumber "4".
- Chvátal_graph diameter "2".
- Chvátal_graph edges "24".
- Chvátal_graph first "Branko".
- Chvátal_graph first "Bruce".
- Chvátal_graph first "Václav".
- Chvátal_graph girth "4".
- Chvátal_graph last "Chvátal".
- Chvátal_graph last "Grünbaum".
- Chvátal_graph last "Reed".
- Chvátal_graph name "Chvátal graph".
- Chvátal_graph namesake Václav_Chvátal.
- Chvátal_graph properties Eulerian_path.
- Chvátal_graph properties Hamiltonian_path.
- Chvátal_graph properties Regular_graph.
- Chvátal_graph properties Triangle-free_graph.
- Chvátal_graph radius "2".
- Chvátal_graph title "Chvátal Graph".
- Chvátal_graph urlname "ChvatalGraph".
- Chvátal_graph vertices "12".
- Chvátal_graph year "1970".
- Chvátal_graph year "1998".
- Chvátal_graph subject Category:4-chromatic_graphs.
- Chvátal_graph subject Category:Individual_graphs.
- Chvátal_graph subject Category:Regular_graphs.
- Chvátal_graph comment "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 (1970).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.".
- Chvátal_graph label "Chvátal graph".
- Chvátal_graph label "Grafo de Chvátal".
- Chvátal_graph label "Grafo de Chvátal".
- Chvátal_graph label "Graphe de Chvátal".
- Chvátal_graph sameAs Chv%C3%A1tal_graph.
- Chvátal_graph sameAs Grafo_de_Chvátal.
- Chvátal_graph sameAs Graphe_de_Chvátal.
- Chvátal_graph sameAs Grafo_de_Chvátal.
- Chvátal_graph sameAs Q3029658.
- Chvátal_graph sameAs Q3029658.
- Chvátal_graph wasDerivedFrom Chvátal_graph?oldid=569357236.
- Chvátal_graph depiction Chvatal_graph.draw.svg.