Connected complementary graphs relative to \(K_{a,b}\) and some Nordhaus-Gaddum type results (Q1355403)

The authors study the edge chromatic number \(\chi_1\), the edge independence number \(\beta_1\) and some related parameters for bipartite graphs and their complements relative to the complete bipartite graph \(K_{a,b}\). They prove tight upper and lower bounds for the sums and the products of each of these parameters for a graph and its relative complement in terms of the order \(a,b\) of the complete bipartite graph relative to which the complement is taken (Nordhaus-Gaddum-type theorems). E.g. if the bipartite graph \(G_2\) is the complement of the bipartite graph \(G_1\) relative to the complete bipartite graph \(K_{a,b}\), \(a\leq b\), and \(G_1\) and \(G_2\) are connected, then \(b\leq\chi_1 (G_1)+ \chi_1(G_2)\leq 2b-2\).