๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A triangle-free circle graph with chromatic number 5

โœ Scribed by A.A. Ageev

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
170 KB
Volume
152
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 and Lehel.

๐Ÿ“œ 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),

Small graphs with chromatic number 5: A
Small graphs with chromatic number 5: A computer search
โœ Tommy Jensen; Gordon F. Royle ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 402 KB

## Abstract In this article we give examples of a triangleโ€free graph on 22 vertices with chromatic number 5 and a __K__~4~โ€free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5โ€critica

Triangles in a complete chromatic graph
Triangles in a complete chromatic graph with three colors
โœ A.W Goodman ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 556 KB

Let Kr~ be the complete graph on N vertices, and assume that each edge is assigned precisly one of three possible colors. An old and difficult problem is to find the minimum number of monochromatic triangles as a function of N. We are not able to solve this problem, but we can give sharp bounds for

On the chromatic number of a random 5-re
On the chromatic number of a random 5-regular graph
โœ J. Dรญaz; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. Pรฉrez; N. Wormald ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 275 KB ๐Ÿ‘ 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5โ€regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5โ€regular graph is as