A note on the complexity of graph parameters and the uniqueness of their realizations

摘要

Let v be some graph parameter and let G be a class of graphs for which v can be computed in polynomial time. In this situation it is often possible to devise a strategy to decide in polynomial time whether v has a unique realization for some graph in G. We first give an informal description of the conditions that allow one to devise such a strategy, and then we demonstrate our approach for three well-known graph parameters: the domination number, the independence number, and the chromatic number.