Graphs, colours, weights and hereditary properties
Andrew G. Thomason · Cambridge University Press eBooks · 2011
Graphs whose edges are coloured with two colours are naturally related to induced subgraphs of ordinary graphs. This leads to an extremal theory for coloured graphs, in which the edges are given weights. We describe the theory, explaining its connections with the study of hereditary graph properties and noting recent progress. Coloured graphs Every graph H corresponds in a natural way to a complete graph on the same set V(H) of vertices, whose edges are coloured red and blue: an edge of the complete graph is coloured red if it is present in H and is coloured blue if it is absent from H . In the normal way of things there is nothing to be gained by thinking about the 2-coloured complete graph instead of the original graph, but there are circumstances in which the 2-coloured representation has merit. This is particularly true if H is an induced subgraph of some other graph, because the presence of the blue edges in the coloured complete graph emphasises that the absence of an edge from H is just as important as the presence of an edge. Various questions about induced subgraphs have been studied quite intensively over the last couple of decades, and it turns out that some of these can be reduced to extremal questions about coloured graphs. This is what motivates the work that is surveyed in this article.