2
$\begingroup$

For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$.

Is there for every graph $G$ a graph $2G$ such that

-- $\chi(2G) = 2\chi(G)$, and

-- $\eta(2G) = 2\eta(G)$?

For each one of the above conditions it is easy to construct a graph $2G$ to $G$ such that the condition holds, but I haven't been able to double both the coloring number and the Hadwiger number at the same time with a "universal construction".

$\endgroup$

1 Answer 1

3
$\begingroup$

Define $K_n'$ to be the graph obtained from the complete graph on $n$ vertices by subdividing each edge once. Let $G$ be a graph with $\chi(G)=c$ and $\eta(G)=h$. Define $2G$ to be the disjoint union of $K_{2h}'$ and $K_{2c}$. Assuming Hadwiger's conjecture, we have $c \leq h$, and so $\eta(2G)= 2 \eta(G)$ and $\chi(2G)=2\chi(G)$ (since $K_n'$ is 2-colourable for all $n$).

Of course, this may not be the type of construction you had in mind, but it works (assuming Hadwiger's conjecture is true).

$\endgroup$

You must log in to answer this question.

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