Non-three-colorable common graphs exist

Abstract

A graph is common if the number of its copies in a graph and its complement is minimized for random graphs. We show that the wheel on six vertices is a common graph.

Keywords

• common graphs
• flag algebra