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