In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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, e.g., including only woody plants with secondary growth, only ...
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 i ...
, the graphs with neither
nor
as
induced subgraph
In 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.
Definition
Formally, let G=(V,E) ...
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 and
David Sumner, 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 ( ; 26March 191320September 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 discrete mathematics, g ...
and
András Hajnal have shown, there exist graphs with arbitrarily large chromatic number and, at the same time, arbitrarily large
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 a luminous spheroid of plasma held together by self-gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night; their immense distances from Earth make them appear as fixed points of ...
, and trees of radius two.
It is also known that, for any tree
, the graphs that do not contain any
subdivision 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