Another infinite sequence of dense triangle-free graphs
The electronic journal of combinatorics, Tome 5 (1998)
The core is the unique homorphically minimal subgraph of a graph. A triangle-free graph with minimum degree $\delta > n/3$ is called dense. It was observed by many authors that dense triangle-free graphs share strong structural properties and that the natural way to describe the structure of these graphs is in terms of graph homomorphisms. One infinite sequence of cores of dense maximal triangle-free graphs was known. All graphs in this sequence are 3-colourable. Only two additional cores with chromatic number 4 were known. We show that the additional graphs are the initial terms of a second infinite sequence of cores.
DOI :
10.37236/1381
Classification :
05C75, 05C35
Mots-clés : core, dense triangle-free graphs, graph homomorphisms
Mots-clés : core, dense triangle-free graphs, graph homomorphisms
@article{10_37236_1381,
author = {Stephan Brandt and Toma\v{z} Pisanski},
title = {Another infinite sequence of dense triangle-free graphs},
journal = {The electronic journal of combinatorics},
year = {1998},
volume = {5},
doi = {10.37236/1381},
zbl = {0898.05067},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1381/}
}
Stephan Brandt; Tomaž Pisanski. Another infinite sequence of dense triangle-free graphs. The electronic journal of combinatorics, Tome 5 (1998). doi: 10.37236/1381
Cité par Sources :