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.


  • 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).

enter image description here

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)$.

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

I think Artem is on the right track with perfection:

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$.

So it seems the statement in question 1 is true.

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.


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.