1
$\begingroup$

Let $G=(V,E)$ be a finite, simple, undirected graph. We say that a partition ${\cal P}$ of $V$ into non-empty subsets of $V$ is connected if any two distinct blocks are connected by an edge, or more formally, if for $p_1\neq p_2\in {\cal P}$ there is $e\in E$ with $$(p_1\cap e)\neq \varnothing\neq (p_2\cap e).$$ The maximum cardinality of any connected partition of $G$ is called the connected partition number $\text{cp}(G)$ of $G$.

The Hadwiger number of a graph $G$, denoted by $\eta(G)$ is the maximum $n$ such that $K_n$ is a minor of $G$. It is not hard to see that for any finite graph $G$, the number $\text{cp}(G)$ is greater or equal to both $\eta(G)$ and the chromatic number $\chi(G)$ of $G$. (As a side note, Hadwiger's famous conjecture claims $\eta(G)\geq \chi(G)$ for any $G$.)

Question. Given a positive integer $k\geq 2$, is there an graph $G=(V,E)$ with $\text{cp}(G) \geq k\cdot\eta(G)$?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I think, we always have $\eta(G)\geqslant {\text cp} (G)$: for a connected partition, contract all edges inside every block. $\endgroup$
    – Fedor Petrov
    Commented Jan 17, 2021 at 13:16
  • 2
    $\begingroup$ @FedorPetrov if I understand the definition correctly, the path on 4 vertices $P_4$ has $cp(P_4) = 3$, using the set partition that puts the two leaves into a single block. $\endgroup$
    – Martin Rubey
    Commented Jan 17, 2021 at 16:39
  • 4
    $\begingroup$ @MartinRubey ah, they need not be connected themselves. Agree. But then there exists even a tree with arbitrarily large $\text{cp}$: for any two blocks $P_i$, $P_j$ choose the vertices $A_{ij}\in P_i$ and $A_{ji}\in P_j$ and join them by an edge. We get many disjoint edges, but the graph is not yet connected. They may be connected by an extra path so that this is still a tree. $\endgroup$
    – Fedor Petrov
    Commented Jan 17, 2021 at 16:45
  • 1
    $\begingroup$ This is now findstat.org/StatisticsDatabase/St001670 $\endgroup$
    – Martin Rubey
    Commented Jan 17, 2021 at 17:01
  • 2
    $\begingroup$ @FedorPetrov So a graph $G$ which contains a matching of size $\binom n2$ has $cp(G)\ge n$? $\endgroup$
    – bof
    Commented Jan 21, 2021 at 12:56

0

Reset to default

You must log in to answer this question.