Nordhaus-Gaddum Sum Problems for Tree-width and Colin de Verdière Parameters

Thursday, October 9, 2014 - 2:00pm - 3:00pm
Lind 305
Leslie Hogben (Iowa State University)
A Nordhaus-Gaddum sum problem for a graph parameter is to determine a tight lower or upper bound for the sum of the parameter evaluated on a graph and on its complement. This talk will survey Nordhaus-Gaddum sum results and open questions for tree-width, the Colin de Verdière type parameters µ and ν, and related parameters (all of the parameters discussed will be defined).

The tight lower bound for tree-width is tw(G)+tw(Ḡ) ≥ G- 2: It has been conjectured that µ(G) + µ(Ḡ) ≥ G ≥ - 2 and ν(G) + ν(Ḡ) ≥ G - 2: Partial
results and other evidence for these conjectures will be discussed.

Upper and lower bounds on the Nordhaus-Gaddum upper multiplier b,
where ν(G) + ν(Ḡ) ≤ bνG for all G, will also be discussed, together with
questions about bounds on upper multipliers for the other parameters.