𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Still another triangle-free infinite-chromatic graph

✍ Scribed by A. Gyárfás

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
48 KB
Volume
30
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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), then B, C are in the same column so BC# E(G). G is infinite-chromatic: Ni c (1,2, . . . } denotes the set of colours used on the vertices of the ith commn in a good coloring of the vertices of G. For i <j the ith column contains a vertex connected to all vertices of the jth column therefore Ni # Nj which implies I UT= 1 Ni I = 00.

📜 SIMILAR VOLUMES

Triangle-free four-chromatic graphs
Triangle-free four-chromatic graphs
✍ Guoping Jin 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 640 KB

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).

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.

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