✦ LIBER ✦

Triangle-free four-chromatic graphs

✍ Scribed by Guoping Jin

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 640 KB
Volume: 145
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00063-o

No coin nor oath required. For personal study only.

✦ Synopsis

For given n, let G be a triangle-free graph of order n with chromatic number at least 4. In this paper, we shall prove a conjecture of H/iggkvist by determining the maximal value of 6(G).

📜 SIMILAR VOLUMES

On minimal 5-chromatic triangle-free gra

On minimal 5-chromatic triangle-free graphs

✍ David Avis 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

## Abstract It is shown that the minimum number of vertices in a triangle‐free 5‐chromatic graph is at least 19.

Still another triangle-free infinite-chr

Still another triangle-free infinite-chromatic graph

✍ A. Gyárfás 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 48 KB

We give a new example of a triangle-free =-chromatic graph: the vertices of G form a WX 00 matrix, V(G) = [S,j], i,. i = 1,2, . . . The vertex Ui,j is connected with every vertex of the (i + j)th column. G is triangle-free: if A has the smallest column-index among {A, B, C} c V(G) and AB, ACE E(G),

Isomorphism of two infinite-chromatic tr

Isomorphism of two infinite-chromatic triangle-free graphs

✍ Zsolt Tuza 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 125 KB

A triangle-free circle graph with chroma

A triangle-free circle graph with chromatic number 5

✍ A.A. Ageev 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 170 KB

It follows from the results of , Gyirfis and Lehel (1985), and Kostochka (1988) that 4 ~x\* ## ~5 where x\* = max {X(G): G is a triangle-free circle graph}. We show that X\* ? 5 and thus X\* = 5. This disproves the conjecture of Karapetyan that X\* = 4 and answers negatively a question of Gyirfis

Triangle-free regular graphs

✍ A.F. Sidorenko 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 152 KB

On triangle-free random graphs

✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 3 views

We show that for every k ≥ 1 and δ > 0 there exists a constant c > 0 such that, with probability tending to 1 as n → ∞, a graph chosen uniformly at random among all triangle-free graphs with n vertices and M ≥ cn 3/2 edges can be made bipartite by deleting δM edges. As an immediate consequence of th