##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 752.05028

**Autor: ** Erdös, Paul; Fajtlowicz, Siemion; Staton, William

**Title: ** Degree sequences in triangle-free graphs. (In English)

**Source: ** Discrete Math. 92, No.1-3, 85-88 (1991).

**Review: ** Authors' abstract: The computer program *Graffity* has conjectured that the chromatic number of a triangle-free graph does not exceed the maximum number of occurrences of an element of the degree sequence. We prove that indeed if no degree occurs more than twice, the graph is bipartite. On the other hand, we prove that every triangle-free graph is an induced subgraph of a triangle-free graph in which no degree occurs more than three times.

**Reviewer: ** C.Chaty (Paris)

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C99 Graph theory

**Keywords: ** degree sequences; triangle-free graphs; chromatic number

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag