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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page