Hajós conjecture

The conjecture of Hajós is a guess from the graph theory . It was in the 1950s by mathematician György Hajós set up and states that a graph that is not less than can be dyed colors, a subdivision of the complete graph on vertices (d. E. The as topological minor ) must contain. In brief: . Roughly speaking, this means that a graph that has a certain chromatic number must contain a certain structure. The term is often used as an abbreviation for the assumption . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle K_{k}}$ ${\displaystyle \chi (G)\geq k\ \Rightarrow \ K_{k}\preceq _{T}G}$ ${\displaystyle (U_{k})}$

For a long time it was assumed that the assumption was correct for everyone . In 1979, however , Paul Catlin published a paper in which he constructed a counterexample for . However, since it also implies, he refuted the presumption for everyone . However, the cases for are correct. The case is still open to this day. ${\displaystyle k}$ ${\displaystyle k=7}$ ${\displaystyle (U_{k+1})}$ ${\displaystyle (U_{k})}$ ${\displaystyle k\geq 7}$ ${\displaystyle k\leq 4}$ ${\displaystyle k=6}$

Carsten Thomassen found further counterexamples after Catlin . However, Thomassen also found that locally planar graphs and triangulations of the projective plane and the torus fulfill the conjecture. Bojan Mohar refuted his further assumption that all triangulations fulfill the assumption.

Paul Erdős and Fajtlowicz proved in 1981 within the framework of probabilistic graph theory that the conjecture is wrong for almost all graphs.

The presumption of Hajós is a tightening of Hadwiger's conjecture is because each topological minor of one can be contracted and thus is also a minor. However, it is not true that every minor is also a topological minor. Although they seem equivalent at first glance, the two assumptions are fundamentally different. Hadwiger's conjecture is about minors, which are rather independent of the drawing of the graph and result in a combinatorial approach. Topological minors, as required in Hajós' conjecture, are topological approaches, i.e. This means that the drawing of the graph is in the foreground. ${\displaystyle K_{k}}$ ${\displaystyle K_{k}}$

There is another (generally unsolved) Hajós conjecture about the circular decomposition of graphs.

Individual evidence

1. ↑ Hajos on a construction of graphs that cannot be n-colored , Wiss. Z. Martin Luther Univ. Halle-Wittenberg. Math.-Nat. Series., Vol. 10, 1961, pp. 116-117.
2. ^ PA Catlin Hajos Graph Coloring Conjecture: Variations and Counterexamples , J. Combinatorial Theory B, Vol. 26, 1979, pp. 268-274
3. ↑ This was proved by Gabriel Dirac in 1952 for k less than or equal to 4 . Dirac A property of 4-chromatic graphs and some remarks on critical graphs , J. London Mathematical Society, Vol. 27, 1952, pp. 85-92
4. ↑ Thomassen Some remarks on Hajos Conjecture , Journal of Combinatorial Theory B, Vol. 93, 2005, p. 95
5. ↑ Mohar Triangulations and the Hajos Conjecture , PDF file
6. ↑ Paul Erdős , Simion Fajtlowicz On the conjecture of Hajos , Combinatorica Vol. 1, 1981, p. 141