The Hadwiger number of complements of some graphs (Q2702750)

An \(H\)-decomposition of a graph \(G\) is a partition of the vertex set \(V(G)\) of \(G\) such that each of its classes induces a connected subgraph of \(G\) and so does the union of any two of its classes. The maximum number of classes of an \(H\)-decomposition of a connected graph \(G\) is the Hadwiger number of \(G\). A theorem concerning the Hadwiger number of the Zykov sum of graphs and a formula for the maximal number of edges of a graph with \(n\) vertices and with the Hadwiger number \(k\) (for certain values of \(n\) and \(k\)) are proved. The main results are formulas for the Hadwiger number of the complement of a graph \(G\) in terms of the vertex covering number of \(G\) under the assumption that \(G\) contains no circuit of length less than 7.