Minimal normal graph covers

الأصل · EN

A graph is normal if it admits a clique cover C and a stable set cover S such that each clique in C and each stable set in S have a vertex in common. The pair (C,S) is a normal cover of the graph. We present the following extremal property of normal covers. For positive integers c,s, if a graph with n vertices admits a normal cover with cliques of sizes at most c and stable sets of sizes at most s, then c+s≥₂(n). For infinitely many n, we also give a construction of a graph with n vertices that admits a normal cover with cliques and stable sets of sizes less than 0.87₂(n). Furthermore, we show that for all n, there exists a normal graph with n vertices, clique number Θ(₂(n)) and independence number Θ(₂(n)). When c or s are very small, we can describe all normal graphs with the largest possible number of vertices that allow a normal cover with cliques of sizes at most c and stable sets of sizes at most s. However, such extremal graphs remain elusive even for moderately small values of c and s.