7
$\begingroup$

A conjecture of Mader implies that for any positive integer $n\geq2$, every graph with average degree at least $3n-4$ contains an $n$-connected subgraph. Mader himself proved this for $n=2,3,4,5,6,7$. In particular, any graph with minimum degree $5$ admits a $3$-connected subgraph, and so any graph with chromatic number at least $6$ admits a $3$-connected subgraph.

Question: Does every graph with chromatic number $5$ already admit a $3$-connected subgraph?

$\endgroup$

1 Answer 1

4
$\begingroup$

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via Hajó's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected. $\square$

On the other hand, every graph with chromatic number $4$ contains a subgraph which is 'almost' $3$-connected.

Claim. Every graph $G$ with $\chi(G)=4$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=4$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 3$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $3$-colourable). Moreover, we must have $\chi(A)=\chi(B)=3$ (otherwise $G'$ is $3$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=3$. Thus, $A+xy$ is $3$-connected, as required. $\square$

Hopefully, for graphs $G$ with $\chi(G)=5$, it is not necessary to add the edge $xy$ to obtain a $3$-connected subgraph.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.