The Coarseness of the Complete Graph

Abstract

The coarseness, c(G) , of a graph G is the maximum number of edge-disjoint, non-planar subgraphs of G . We consider only the complete graph, K p , on p vertices here. For p = 3r, Erdös conjectured that the coarseness was , but it has been shown (1) that 1 where square brackets denote integer part.