Independence in graphs with maximum degree four

Date

1982

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Let C denote the class of simple triangle-free graphs with maximum degree at most four. We construct graphs of C which are critical with respect to independence and which provide information about the minimum number of edges possible in graphs of C. Let r(k) denote the smallest integer such that every graph in C with r(k) vertices has independence at least k. We evaluate r(k) for all k and as a corollary we obtain 4/13 as the best possible lower bound for the independence ratio for graphs in C.

Description

Keywords

Graph theory

Citation