1
$\begingroup$

A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too)

Start with a simple planar graph $H$ where every face is a 4-cycle. Let $H_s$ be the graph obtained by stellating every face of $H$, i.e., by inserting into every face of $H$ a new vertex that is adjacent to all vertices of the face.

We know that $H$ is a perfect graph (since any bipartite graph is perfect), but is any $H_s$ a perfect graph? I hesitate to make a definitive statement, but I have checked a few examples, and it seems to hold.

enter image description here

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The graph $H_s$ has clique number $3$ (since $H$ has clique number $2$, and a clique in $H_s$ cannot include more than one stellating vertex). It also has chromatic number $3$ (keep the $2$-coloring of $H$ and give all the stellating vertices a third color). So we can try to prove that $H_s$ is perfect directly from the definition: we can check that if $G_s$ is an induced subgraph of $H_s$, then the clique number $\omega(G_s)$ and the chromatic number $\chi(G_s)$ are equal.

Let $G_s$ be an induced subgraph of $H_s$, with $G$ the common subgraph of $G_s$ and $H$. If $G_s$ has no vertices, then $\omega(G_s)=\chi(G_s)=0$. Otherwise, if it has no edges, then $\omega(G_s)=\chi(G_s)=1$. If $G_s$ has both vertices and edges, then $2 \le \omega(G_s) \le \chi(G_s) \le 3$, and we can try to $2$-color $G_s$ by the following strategy:

  1. Keep the $2$-coloring of $G$ that we know exists because $G$ is bipartite.
  2. For each stellating vertex, try to give it a color not present on any of its neighbors.

If this strategy succeeds, then $\omega(G_s) = \chi(G_s) = 2$. If it fails, then there is a stellating vertex $x$ which has two neighbors of opposite colors. But then those two neighbors are consecutive vertices of the face that $x$ stellated - so, together with $x$, they form a triangle. In this case, $\omega(G_s) = \chi(G_s)=3$.

It follows that the stellated graph $H_s$ is guaranteed to be perfect.

$\endgroup$
5
  • $\begingroup$ I think that your proof is probably correct. However, I still have some confusion. Perhaps in a 3-coloring of a induced subgraph $G$, $H$ is not 2-colored but 3-colored. Based on this fundamental concern, I pose the question math.stackexchange.com/questions/4934636/… to verify if my concern is valid. $\endgroup$
    – licheng
    Commented Jun 19 at 7:37
  • $\begingroup$ That is, your discussion at the beginning might have assumed that all vertices of $H$ are 2-colored. It feels like some analysis was overlooked. $\endgroup$
    – licheng
    Commented Jun 19 at 7:50
  • $\begingroup$ I thought of a slightly simpler proof. When I have time, I will try to add it. $\endgroup$
    – licheng
    Commented Jun 19 at 9:14
  • 1
    $\begingroup$ Well, I think that something about my writeup should be cleared up, because "let $G$ be an induced subgraph of $G$" is incoherent - I'll edit in a moment. But we don't have the problem you're imagining. We are not considering some maliciously given coloring; I specifically said that we $3$-color $H_s$ by first $2$-coloring $H$, and then giving all the stellating vertices a third color. $\endgroup$
    – Misha Lavrov
    Commented Jun 19 at 16:45
  • $\begingroup$ I understand. Thank you. Indeed, $H_s$ has such a 3-coloring scheme in advance. Other coloring methods do not matter. $\endgroup$
    – licheng
    Commented Jun 20 at 8:25

You must log in to answer this question.

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