# Chromatic number of G+v where G is a cograph

Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v.

Notations:

• Denote by $\chi(G)$ the chromatic number of a graph $G$.

• Let $V(G)$ denote the vertices of $G$. For any vertex $v\in V(G)$, denote by $N(v)$ the neighbors of $v$ and $N[v]=N(v)+v$ the closed neighborhood of $v$. Let $A\subseteq V(G)$, denote by $\langle A \rangle_{G}$ be the induced subgraph of $A$ of $G$.

• Let $G$ be an undirected simple graph, and $H=G+v$ be a graph such that $G=H-v$, i.e., $G$ is the graph obtained by deleting $v$ from $H$. This type of notation is introduced in the paper Parameterized complexity of vertex colouring. For a graph class $\mathcal{F}$, let $\mathcal{F}+kv$ denote the graphs which can be built by adding at most $k$ vertices to a graph in $\mathcal{F}$.

Question 1: Is the following statement true?

$\chi(G+v)=\chi(G)+1$ if and only if $\chi(\langle N(v) \rangle)=\chi(G)$, where $G$ is a cograph.

The "if" direction is easy, because $\chi(G+v) \le \chi(G)+1$ and $\chi(\langle N[v] \rangle) = \chi(\langle N(v) \rangle) + 1$. For general simple graph $G$, the "only if" direction is not true. For example, let $G$ be a $P_4$ (path of 4 vertices) and $G+v$ be a $C_5$ (cycle of 5 vertices).

Question 2: If the proposition in question 1 is false. Is it easy to determine $\chi(G+v)$, where $G$ is a cograph.

Update: Jim showed than cograph+v is a subset of the class of perfect graph. Also he actually proved another more general theorem.

For any perfect graph $G$, $\chi(G)=\chi(G-v)+1$ if and only if $\chi(\langle N(v)\rangle) = \chi(G-v)$.

• Isn't $P_4$ a perfect graph? – Artem Kaznatcheev Mar 4 '14 at 2:59
• What's the question here ? – Suresh Venkat Mar 4 '14 at 3:20
• @ArtemKaznatcheev Thank you for the comment. I am actually working on "cograph+v". – Peng Zhang Mar 4 '14 at 3:30
• @SureshVenkat Thanks. I edited the question and now it has two specific questions. – Peng Zhang Mar 4 '14 at 3:31

As cographs are $P_4$-free, cograph+v is $C_5$-free (and $C_{2k+1}$-free and $\overline{C}_{2k+1}$-free, $k>1$) and so they are perfect graphs.
This means the only thing that is pushing the chromatic number up is clique size. So if $\chi(G+v) = \chi(G) + 1$, it is because v has increased the maximum clique size, which means that $N(v)$ must have had a clique of size $\chi(G)$ and so $\langle N(v)\rangle_G$ had the same chromatic number as $G$.
But even without it, since cograph+v can't have any large induced cycles, it is contained in the set of weakly chordal graphs. A graph $G$ is a weakly chordal graph if for every cycle of length at least 5 in $G$ and $\overline{G}$, there is a chord. Weakly chordal graphs are a subset of perfect graphs and there are various efficient algorithms for a number of optimization problems on weakly chordal graphs, such as colouring.