Connected complementary graphs relative to K_a,b and some Nordhaus-Gaddum type results

MaRDI QIDQ1355403zbMATH OpenFDO

Authors S. Sivagurunathan, Saraju P. Mohanty

Publication date 24 September 1997

Published in Indian Journal of Pure \& Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphedge chromatic numberedge independence numberNordhaus-Gaddum-type theoremsrelative complement

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

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\).

Recommendations

• The connectivity of a bipartite graph and its bipartite complementary graph
• scientific article; zbMATH DE number 500499
• Complementary graphs and the chromatic number
• A survey of Nordhaus-Gaddum type relations

Cited in

(3)

• On the Strongly Connected and Biconnected Components of the Complement of Graphs
• [1,2]-Complementary connected domination number of graphs-III
• The connectivity of a bipartite graph and its bipartite complementary graph

This page was built for publication: Connected complementary graphs relative to \(K_{a,b}\) and some Nordhaus-Gaddum type results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1355403)