Enumeration of Bicolourable Graphs

Abstract

In a previous paper (2), one of us has derived a formula for the counting series for bicoloured graphs.2 These are graphs each of whose points has been coloured with exactly one of two colours in such a way that every two adjacent points have different colours. In this paper we first enumerate bicoloured graphs without isolated points and connected bicoloured graphs. This leads us to corresponding problems for bicolourable graphs. Such a graph has the property that its points can be coloured with two colours so as to obtain a bicoloured graph.