2
$\begingroup$

To be minimally imperfect means that the graph is not perfect and deleting any vertex results in a perfect graph.

To be normal means that there exists a family of independent sets $\{A_1, A_2, \dots, A_n\}$ that cover the vertex set and a family of cliques $\{B_1,B_2,\dots,B_m\}$ that also cover the vertex set such that $A_i \cap B_j \neq \emptyset$ for all $i,j$.

I have been trying to construct some minimally imperfect graph, but I have not been successful.

Any thoughts?

$\endgroup$
1
  • $\begingroup$ By the strong perfect graph theorem, the only minimally imperfect graphs are the odd cycles and their complements. $\endgroup$ Apr 25, 2019 at 14:19

1 Answer 1

2
$\begingroup$

Here is an example: the graph $C_9$, where if we number the vertices $1,2,3,4,5,6,7,8,9$ around the cycle, the independent sets are $\{1,3,5,8\}$ (in yellow), $\{2,4,6,8\}$ (in red), and $\{2,5,7,9\}$ (in blue). The cliques are the edges $12, 23, 45, 56, 78, 89$: the solid edges in the diagram below. (The dashed edges are the other edges of the cycle.)

enter image description here

The minimally imperfect graphs are just the odd cycles and their complements: by the strong perfect graph theorem, imperfect graphs are precisely the graphs which contain one of these as an induced subgraph, and if they contain anything else, they're not minimal because we can delete the "anything else". We can assume we're working with an odd cycle, because taking the complement just swaps the roles of cliques and independent sets.

We need at least three independent sets to cover an odd cycle, and each independent set has at least one edge it misses entirely (which cannot be in the clique cover). So our clique cover will probably be missing at least three edges, which means we need to go to $C_9$ to be able to space those edges out properly (as seen above). Once we choose the edges in this way, there is a natural choice of independent sets to take: for each edge not in the clique cover, choose the maximum independent set disjoint to that edge (which will intersect every other edge in the graph).

This results in the example above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.