Journal or Book Title
Electronic Journal of Combinatorics
We establish the bounds 4 3 6 b 6 b 6 p 2, where b and b are the Nordhaus-Gaddum sum upper bound multipliers, i.e., (G)+(G) 6 bjGj and (G)+(G) 6 bjGj for all graphs G, and and are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for and is conjectured to be jGj 2, and if these parameters are replaced by the maximum nullity M(G), this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.
The [Copyright] Owner hereby grants to the Journal a worldwide, irrevocable, royalty free license to publish or distribute the Work, to enter into arrangements with others to publish or distribute the Work, and to archive the Work. The Owner agrees that further publication of the Work, with the same or substantially the same content as appears in the Journal, will include an acknowledgement of prior publication in the Journal.
Barrett, Wayne; Fallat, Shaun M.; Hall, H. Tracy; and Hogben, Leslie, "Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters" (2013). Mathematics Publications. 62.