In
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 conne ...
, the Gyárfás–Sumner conjecture asks whether, for every
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
and
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
, the graphs with neither
nor
as
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
s can be
properly colored using only a constant number of colors. Equivalently, it asks whether the
-free graphs are
-bounded.
It is named after
András Gyárfás
András Gyárfás (born 1945) is a Hungarian mathematician who specializes in the study of graph theory. He is famous for two conjectures:
* Together with Paul Erdős he conjectured what is now called the Erdős–Gyárfás conjecture which sta ...
and
David Sumner
David P. Sumner is an American mathematician known for his research in graph theory. He formulated Sumner's conjecture that tournaments are universal graphs for polytrees in 1971, and showed in 1974 that all claw-free graphs with an even number of ...
, who formulated it independently in 1975 and 1981 respectively. It remains unproven.
In this conjecture, it is not possible to replace
by a graph with cycles. As
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
and
András Hajnal
András Hajnal (May 13, 1931 – July 30, 2016) was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.
Biography
Hajnal was born on 13 May 1931, have shown, there exist graphs with arbitrarily large chromatic number and, at the same time, arbitrarily large
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
. Using these graphs, one can obtain graphs that avoid any fixed choice of a cyclic graph and clique (of more than two vertices) as induced subgraphs, and exceed any fixed bound on the chromatic number.
The conjecture is known to be true for certain special choices of
, including
paths,
stars
A star is an astronomical object comprising a luminous spheroid of plasma held together by its gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night, but their immense distances from Earth ma ...
, and trees of radius two.
It is also known that, for any tree
, the graphs that do not contain a
subdivision
Subdivision may refer to:
Arts and entertainment
* Subdivision (metre), in music
* ''Subdivision'' (film), 2009
* "Subdivision", an episode of ''Prison Break'' (season 2)
* ''Subdivisions'' (EP), by Sinch, 2005
* "Subdivisions" (song), by Rus ...
of
are
-bounded.
References
External links
Graphs with a forbidden induced tree are chi-bounded Open Problem Garden
{{DEFAULTSORT:Gyarfas-Sumner conjecture
Graph coloring
Conjectures
Unsolved problems in graph theory