Computational Complexity of Graphs
Stasys P. Jukna · 2013
Computational complexity of graphs is the smallest number of union and intersection operations required to generate them when starting from stars. An intriguing aspect of this measure is its connection with the circuit complexity of Boolean functions and, in particular, with the P versus NP problem. We describe this connection and survey known bounds on the star complexity of explicit graphs.