<p>I think Artem is on the right track with perfection:</p>

<p>As cographs are $P_4$-free, cograph+v is $C_5$-free (and $C_{2k+1}$-free and $\overline{C}_{2k+1}$-free, $k&gt;1$) and so they are perfect graphs.</p>

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

<p>So it seems the statement in question 1 is true.</p>

<p>But even without it, since cograph+v can't have any large induced cycles, it is contained in the set of <strong>weakly chordal graphs</strong>. 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.</p>

CC BY-SA 3.0
2014-03-04T08:25:34.930Z
2014-03-04T18:31:19.013Z
2014-03-04T18:31:19.013Z
JimN
<p><a href="http://en.wikipedia.org/wiki/Chromatic_number#Definition_and_terminology" rel="nofollow noreferrer">Cograph</a> 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 <strong>cograph+v</strong>.</p>

<p><strong>Notations</strong>:</p>

<ul>
<li><p>Denote by $\chi(G)$ the <a href="http://en.wikipedia.org/wiki/Chromatic_number#Definition_and_terminology" rel="nofollow noreferrer">chromatic number</a> of a graph $G$. </p></li>
<li><p>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$.</p></li>
<li><p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0166218X02002421" rel="nofollow noreferrer">Parameterized complexity of vertex colouring</a>. 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}$.</p></li>
</ul>

<p><strong>Question 1</strong>:
Is the following statement true?</p>

<p>$\chi(G+v)=\chi(G)+1$ if and only if $\chi(\langle N(v) \rangle)=\chi(G)$, where $G$ is a <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow noreferrer">cograph</a>.</p>

<p>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).</p>

<p><img src="https://i.sstatic.net/4ubPi.png" alt="enter image description here"></p>

<p><strong>Question 2</strong>:
If the proposition in question 1 is false. Is it easy to determine $\chi(G+v)$, where $G$ is a <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow noreferrer">cograph</a>. </p>

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

<p>For any <a href="http://en.wikipedia.org/wiki/Perfect_graph" rel="nofollow noreferrer">perfect graph</a> $G$, $\chi(G)=\chi(G-v)+1$ if and only if $\chi(\langle N(v)\rangle) = \chi(G-v)$.  </p>

CC BY-SA 3.0
2014-03-04T02:59:19.270Z
Isn't $P_4$ a perfect graph?
Artem Kaznatcheev
CC BY-SA 3.0
2014-03-04T03:20:48.303Z
What's the question here ?
Suresh Venkat
CC BY-SA 3.0
2014-03-04T03:30:53.830Z
@ArtemKaznatcheev Thank you for the comment. I am actually working on "cograph+v".
Peng Zhang
CC BY-SA 3.0
2014-03-04T03:31:57.193Z
@SureshVenkat Thanks. I edited the question and now it has two specific questions.
Peng Zhang
<graph-theory><graph-colouring><perfect-graph><cograph>
Chromatic number of G+v where G is a cograph
Peng Zhang
# Chromatic number of G+v where G is a cograph

(Asked by: username_0 on 2014-03-04)

[Cograph](http://en.wikipedia.org/wiki/Chromatic_number#Definition_and_terminology) 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](http://en.wikipedia.org/wiki/Chromatic_number#Definition_and_terminology) 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](http://www.sciencedirect.com/science/article/pii/S0166218X02002421). 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](http://en.wikipedia.org/wiki/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](https://i.sstatic.net/4ubPi.png)

**Question 2**:
If the proposition in question 1 is false. Is it easy to determine $\chi(G+v)$, where $G$ is a [cograph](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Perfect_graph) $G$, $\chi(G)=\chi(G-v)+1$ if and only if $\chi(\langle N(v)\rangle) = \chi(G-v)$.

**Tags:** graph-theory, graph-colouring, perfect-graph, cograph

> **Comments:**
> **username_1**: Isn't $P_4$ a perfect graph?  
> **username_2**: What's the question here ?  
> **username_0**: @ArtemKaznatcheev Thank you for the comment. I am actually working on "cograph+v".  
> **username_0**: @SureshVenkat Thanks. I edited the question and now it has two specific questions.  

---

## 1 answers

### Answer by username_3 on 2014-03-04. Score: 8 | Accepted answer

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.


---

