1
$\begingroup$

Definition of 'replication of $v$' is

Suppose $v \in V(G)$. Replication of $v$ is constructing $G'$ by adding a new vertex $v'$ such that $N_{G'}(v')=N_G(v) \cup \{v\}$.

And the following statement is well-known fact(you can find a proof by googling).

Replication of a single vertex conserves perfectivity, i.e., $G'$ obtained from a perfect graph $G$ by replication of $v \in V(G)$ is still perfect.

But I am curious whether the following statement is also true:

$G''$ obtained from $G$ by adding a new vertex $v''$ such that $N_{G''}(v'')=N_G(v)$ is perfect.

Adding $v''$ looks similar to the replication, but it does not contain $v$ in neighborhood of $v''$.
I could not find any counterexample to disprove it.
And proving it seems to be different from the proof of the first statement, so I cannot follow its steps.
Would you help me?

$\endgroup$

1 Answer 1

2
$\begingroup$

If we pass to the complement, this is just a replication. But passing to a complement preserves the class of perfect graphs (a theorem of Lovasz, previously conjecture of Berge).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .