In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Chvátal graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

with 12 vertices and 24 edges, discovered by

Václav Chvátal Václav (Vašek) Chvátal () is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada and a Visiting Professor at Charles University in Prague. He has published e ...

in 1970. It is the smallest graph that is triangle-free, 4-regular, and 4-chromatic.

Coloring, degree, and girth

The Chvátal graph 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 In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

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 In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...

, which has 11 vertices but has maximum degree 5 and is not regular. 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\ge 3

and

\ell\ge 3

there exist

k

-chromatic graphs with girth

\ell

. In connection with these two results and several examples including the Chvátal graph,

Branko Grünbaum Branko Grünbaum ( he, ברנקו גרונבאום; 2 October 1929 – 14 September 2018) was a Croatian-born mathematician of Jewish descentbig 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

\Delta

and

maximum clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

size

\omega

must have chromatic number

\chi(G)\le\left\lceil\frac\right\rceil.

The case

\omega=2

of this conjecture follows, for sufficiently large

\Delta

, 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,

(\Delta+\omega+1)/2=7/2

, a number that is less than the chromatic number but that becomes equal to the chromatic number when rounded up.

Other properties

This graph is not

vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...

: its

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

has one orbit on vertices of size 8, and one of size 4. The Chvátal graph is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

, and plays a key role in a proof by that it is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

to determine whether a triangle-free Hamiltonian graph is 3-colorable. The characteristic polynomial of the Chvátal graph is

(x-4) (x-1)^4 x^2 (x+1) (x+3)^2 (x^2+x-4)

. The

Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...

of the Chvátal graph has been computed by . The

independence number Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...

of this graph is 4.

Gallery

File:Chvatal graph 4COL.svg, The

of the Chvátal graph is 4. File:chvatal graph 4color edge.svg, The

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...

of the Chvátal graph is 4. File:Chvatal Lombardi.svg, The Chvátal graph is

. File:Chvátal graph.svg, Alternative drawing of the Chvátal graph.

References

External links

* {{DEFAULTSORT:Chvatal graph Individual graphs Regular graphs