𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Triangulations and the Hajós conjecture

✍ Scribed by Vojtěch Rödl; Jan Zich

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
325 KB
Volume
59
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In his recent work Thomassen [J Combin Theory Ser B 93 (2005), 95–105] discussed various refinements of Hajós conjecture. Shortly after Mohar [Electr J Combin 12 (2005), N15] provided an answer to Thomassen's Conjecture 6.5, and proposed a possible extension. The aim of this article is to address Mohar's suggestion. In particular, we prove that, for infinitely many integers m, there exists a graph on m vertices forming a triangulation of an orientable surface so that it does not contain a subdivision of a clique of size $O(m^{1/2})$ , and its chromatic number is at least $m^{{2/3} + o(1)}$. The main part of the proof is to show that the random graph can be almost covered by oriented triangles which do not contain certain forbidden configurations. We use a technique similar to the ones of Archdeacon and Grable [Discrete Math 142(1–3)(1995), 21–37] and Thomas and the first author [Random Struct Algorithms 6(1) (1995), 1–12]. We obtain a strengthening by replacing the “nibble” method by “random bites” used by Alon et al. [Israel J Math 100 (1997), 171–187]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 293–325, 2008

📜 SIMILAR VOLUMES

Hajós' conjecture and small cycle double
Hajós' conjecture and small cycle double covers of planar graphs
✍ Karen Seyffarth 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 865 KB

## Seyffarth, K., Hajos' conjecture and small cycle double covers of planar graphs, Discrete Mathematics 101 (1992) 291-306. We prove that every simple even planar graph on n vertices has a partition of its edge set into at most [(n -1)/2] cycles. A previous proof of this result was given by Tao,

On the Loebl–Komlós–Sós conjecture
On the Loebl–Komlós–Sós conjecture
✍ Cristina Bazgan; Hao Li; Mariusz Woźniak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

The Loebl±Komlo  s±So  s conjecture says that any graph G on n vertices with at least half of vertices of degree at least k contains each tree of size k. We prove that the conjecture is true for paths as well as for large values of k(k ! n À 3).

The Hajós Factorization of Elementary 3-
The Hajós Factorization of Elementary 3-Groups
✍ Khalid Amin 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

If G is a finite abelian group and n ) 1 is an integer, we say that G has the Hajos n-property, or is n-good if from each decomposition G s S S . . . S of G ´1 2 n into a direct product of subsets, it follows that at least one of the S is periodic, i Ä 4 meaning that there exists x g G y e such that

The Erdős-Sós Conjecture for trees of di
The Erdős-Sós Conjecture for trees of diameter four
✍ Andrew McLennan 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

## Abstract The Erdős‐Sós Conjecture is that a finite graph __G__ with average degree greater than __k__ − 2 contains every tree with __k__ vertices. Theorem 1 is a special case: every __k__‐vertex tree of diameter four can be embedded in __G__. A more technical result, Theorem 2, is obtained by ex