Gyárfás–Sumner conjecture

Last updated
Unsolved problem in mathematics:

Does forbidding both a tree and a clique as induced subgraphs produce graphs of bounded chromatic number?

In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree and complete graph , the graphs with neither nor as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whether the -free graphs are -bounded. [1] It is named after András Gyárfás and David Sumner, who formulated it independently in 1975 and 1981 respectively. [2] [3] It remains unproven. [4]

In this conjecture, it is not possible to replace by a graph with cycles. As Paul Erdős and András Hajnal have shown, there exist graphs with arbitrarily large chromatic number and, at the same time, arbitrarily large girth. [5] 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. [1]

The conjecture is known to be true for certain special choices of , including paths, [6] stars, and trees of radius two. [7] It is also known that, for any tree , the graphs that do not contain any subdivision of are -bounded. [1]

Related Research Articles

<span class="mw-page-title-main">Graph coloring</span> Methodic assignment of colors to elements of a graph

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 of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

<span class="mw-page-title-main">Clique (graph theory)</span> Adjacent subset of an undirected graph

In the mathematical area of graph theory, a clique 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 is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

<span class="mw-page-title-main">Extremal graph theory</span>

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

András Gyárfás is a Hungarian mathematician who specializes in the study of graph theory. He is famous for two conjectures:

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Paul Seymour (mathematician)</span> British mathematician

Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Triangle-free graph</span> Graph without triples of adjacent vertices

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

<span class="mw-page-title-main">Hedetniemi's conjecture</span> Conjecture in graph theory

In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.

András Hajnal 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.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

<span class="mw-page-title-main">Half graph</span> Type of graph in mathematics

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

In graph theory, a -bounded family of graphs is one for which there is some function such that, for every integer the graphs in with can be colored with at most colors. This concept and its notation were formulated by András Gyárfás. The use of the Greek letter chi in the term -bounded is based on the fact that the chromatic number of a graph is commonly denoted .

References

  1. 1 2 3 Scott, A. D. (1997), "Induced trees in graphs of large chromatic number", Journal of Graph Theory , 24 (4): 297–311, CiteSeerX   10.1.1.176.1458 , doi:10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.3.CO;2-X, MR   1437291
  2. Gyárfás, A. (1975), "On Ramsey covering-numbers", Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 10, Amsterdam: North-Holland, pp. 801–816, MR   0382051
  3. Sumner, D. P. (1981), "Subtrees of a graph and the chromatic number", The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, pp. 557–576, MR   0634555
  4. Chudnovsky, Maria; Seymour, Paul (2014), "Extending the Gyárfás-Sumner conjecture", Journal of Combinatorial Theory , Series B, 105: 11–16, doi: 10.1016/j.jctb.2013.11.002 , MR   3171779
  5. Erdős, P.; Hajnal, A. (1966), "On chromatic number of graphs and set-systems" (PDF), Acta Mathematica Academiae Scientiarum Hungaricae , 17 (1–2): 61–99, doi: 10.1007/BF02020444 , MR   0193025
  6. Gyárfás, A. (1987), "Problems from the world surrounding perfect graphs", Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastosowania Matematyki, 19 (3–4): 413–441 (1988), MR   0951359
  7. Kierstead, H. A.; Penrice, S. G. (1994), "Radius two trees specify χ-bounded classes", Journal of Graph Theory , 18 (2): 119–129, doi:10.1002/jgt.3190180203, MR   1258244