3
$\begingroup$

For any set $X$, let $[X]^2=\big\{\{x,y\}: x\neq y\in X\big\}$. If $G=(V,E)$ is a simple undirected graph and $e\in E$, let $G\setminus e = \big(V\setminus e, E \cap [V\setminus e]^2\big)$.

If $G=(V,E)$ is a finite graph, let $\omega(G)$ be the size of the largest clique in $G$ and let $\chi(G)$ be the chromatic number.

Question. Is there a finite graph $G=(V,E)$ and $e\in E$ such that $\chi(G\setminus e)= \chi(G)-2$ and $\omega(G\setminus e) = \omega(G)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ If the "double-critical graph conjecture" openproblemgarden.org/op/double_critical_graph_conjecture is correct, the answer to the question is no. $\endgroup$
    – Louis Esperet
    Commented Jul 4 at 6:49
  • 2
    $\begingroup$ @LouisEsperetHow does that follow? The OP's graph doesn't have to be double-critical, does it? There need only be one pair of adjacent vertices whose removal lowers the chromatic number by $2$. $\endgroup$
    – bof
    Commented Jul 4 at 9:33

1 Answer 1

Reset to default
6
$\begingroup$

Let $H$ be a graph with $\omega(H)=2$ and $\chi(H)=4$, say the Grötzsch graph. Let $G$ be the graph obtained by taking the disjoint union $H\cup K_2\cup K_4$ and adding edges joining both vertices in $K_2$ to all vertices in $H$. Then $\omega(G)=4$ and $\chi(G)=6$. If $e$ is the edge joining the two vertices in $K_2$, then $G\setminus e=H\cup K_4$ and $\omega(G\setminus e)=\chi(G\setminus e)=4$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can this be modified to have $G$ connected, or even $G \setminus e$? $\endgroup$
    – Daniel Weber
    Commented Jul 4 at 11:21
  • 1
    $\begingroup$ @Daniel Weber by adding one vertex, joined by a path of length 2 with one vertex in $H$, one vertex in $K_2$, one vertex in $K_4$? $\endgroup$
    – Fedor Petrov
    Commented Jul 4 at 11:54
  • $\begingroup$ @DanielWeber Identify one of the vertices in $K_4$ with one of the vertices in$H$. $\endgroup$
    – bof
    Commented Jul 4 at 16:34

You must log in to answer this question.

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