Chromatic numbers of competition graphs
Lundgren, J. Richard
Merz, Sarah K.
Rasmussen, Craig W.
MetadataShow full item record
Previous work on competition graphs has emphasized characterization, not only of the competition graphs themselves but also of those graphs whose competition graphs are chordal or interval. The latter sort of characterization is of interest when a competition graph that is easily colorable would be useful, e.g. in a scheduling or assignment problem. This leads naturally to the following question: Given a graph G, does the structure of G tell us anything about the chromatic number X of the competition graph C(G)? We show that in some cases we can calculate this chromatic number exactly, while in others we can place tight bounds on it.
Showing items related by title, author, creator and subject.
Capizzi, David Alan (Monterey, California : Naval Postgraduate School, 1979-12);This study was undertaken to investigate the need to increase competition at the subcontract level in Government acquisition. Current Government acquisition policies include the preference for competitive subcontracting*, ...
Increasing competitive actions: a focus on technical data rights associated with non-commercial hardware items Liedke, Eric J.; Simonis, Jeffrey D. (Monterey, California: Naval Postgraduate School, 2014-06);This project reviewed the key laws and the Department of Defense’s (DOD’s) current policies pertaining to competition and the acquisition of technical data rights, as it applies to non-commercial hardware items. Competition ...
Cunha, Jesse M.; Augenblick, Ned (2012-07);We explore the effects of competitive and cooperative motivations on contributions in a field experiment. 10,000 potential political donors received solicitations referencing past contribution behavior of members of the ...