Skip to main content
deleted 155 characters in body
Source Link

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(C_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. There has to be a vertex of color $2$ among $v_8, v_1, v_3$. If $f(v_8) = 2$, then we can take $v_8, v_2$ and one of $v_5, v_6$; similarly for $f(v_3) = 2$. IfSince $f(v_1) = 2$, then we can take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(C_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. There has to be a vertex of color $2$ among $v_8, v_1, v_3$. If $f(v_8) = 2$, then we can take $v_8, v_2$ and one of $v_5, v_6$; similarly for $f(v_3) = 2$. If $f(v_1) = 2$, then we take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(C_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. Since $f(v_1) = 2$, we can take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.

edited body
Source Link

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(G_9) = 3$$\chi(C_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. There has to be a vertex of color $2$ among $v_8, v_1, v_3$. If $f(v_8) = 2$, then we can take $v_8, v_2$ and one of $v_5, v_6$; similarly for $f(v_3) = 2$. If $f(v_1) = 2$, then we take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(G_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. There has to be a vertex of color $2$ among $v_8, v_1, v_3$. If $f(v_8) = 2$, then we can take $v_8, v_2$ and one of $v_5, v_6$; similarly for $f(v_3) = 2$. If $f(v_1) = 2$, then we take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(C_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. There has to be a vertex of color $2$ among $v_8, v_1, v_3$. If $f(v_8) = 2$, then we can take $v_8, v_2$ and one of $v_5, v_6$; similarly for $f(v_3) = 2$. If $f(v_1) = 2$, then we take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.

Source Link

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(G_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. There has to be a vertex of color $2$ among $v_8, v_1, v_3$. If $f(v_8) = 2$, then we can take $v_8, v_2$ and one of $v_5, v_6$; similarly for $f(v_3) = 2$. If $f(v_1) = 2$, then we take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

  • $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

  • $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

  • $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.