2
$\begingroup$

Let $G=(V,E)$ be an infinite simple, undirected graph with $\chi(G) \geq \aleph_0$. Is there a minor $M$ of $G$ such that

  1. $M\not\cong G$, and
  2. $\chi(M)=\chi(G)$

?

$\endgroup$
  • $\begingroup$ Let $e$ be an edge of $G$ and let $M=G-e$. Doesn't this already work? Clearly $M$ is a minor of $G$ and $M$ is not isomorphic to $G$. Suppose to the contrary that $\chi(M)<\chi(G)$. Colour $M$ properly with $\chi(M)$ colours and then introduce a new colour and use it on one of the endpoints of $G$. This gives a proper colouring of $G$ and the number of colours is less than $\chi(G)$. $\endgroup$ – Jon Noel Jul 7 '17 at 23:54
  • $\begingroup$ @Jon Noel: Well, the subgraph $M$ you describe may very well be isomorphic to $G$. For example if $G$ consists of an infinite matching and infinitely many isolated vertices. $\endgroup$ – monkeymaths Jul 10 '17 at 12:09
  • $\begingroup$ @monkeymaths ah yes, that is a flaw in my logic. Still, I see no good reason why you can't find $M$ as a subgraph. Does the OP have a good reason for asking for $M$ as a minor? $\endgroup$ – Jon Noel Jul 10 '17 at 12:21
  • 1
    $\begingroup$ I think the answer should be affirmative. I have a strategy of proof. Firstly prove by induction to show that a graph with chromatic number greater than $n$ implies it has (got only by contracting vertices) $K_n$ as its minor. Then show the graph has either has $K_{\infty}$ as its minor or it has a minor which consists of the disjoint union of $K_{n}$ for all natural number $n$. $\endgroup$ – Jiachen Yuan Jul 15 '17 at 5:02
  • 2
    $\begingroup$ Oops, I think there is an easier solution, that is for any $G$ with infinite chromatic number will have at least two different(up to isomorphism) minors. Say, since the chromatic number is infinite, that means you can remove an vertex or remove all edges of a vertex to create an isolated point without changing its chromatic number. Therefore, it means that you can have a minor of exact one isolated vertex and a minor with no isolated vertex. By the way there is a graph $G$ such that $ \chi (G) = \omega_{1}$ and $G$ has no minor $K_{\omega_{1}}$ $\endgroup$ – Jiachen Yuan Jul 16 '17 at 6:56
4
$\begingroup$

For every such $G$ there is an $M$ satisfies your requirement.

It is enough to show that for every graph $G$ with infinite chromatic number has two minors $G_{0}$ and $G_{1}$ such that

$(i)$ $G_{0}$ has no isolated vertex and $G_{1}$ has exact one isolated vertex, and

$(ii)$ $\chi(G_{0}) = \chi(G_{1}) = \chi(G)$.

Proof:

Case 1: If $G$ has at least one isolated vertices, then remove all of them to get $G_{0}$ and remove all but one of them to get $G_{1}$.

Case 2: If $G$ has no isolated vertices, choose one of its vertices, $\nu_{0}$, and remove all of edges which adjacent to $\nu_{0}$ then remove all of its isolated vertices (if there are any) other than $\nu_{0}$. We get our $G_{1}$. It is easy to see that $ \chi(G_{1}) = \chi(G)$. Since if there is a coloring function $c$ maps $V(G_{1})$ to $\kappa \geq \omega$, then let $C$ be the following map from $V(G)$ to $\kappa$:

$(a)$ $C(\nu) = c(\nu) + 2$ if $\nu$ is neither $\nu_{0}$ nor a leaf connected to $\nu_{0}$,

$(b)$ $C(\nu) = 1$ if $\nu$ is a leaf connected to $\nu_{0}$,

$(c)$ $C(\nu_{0}) = 0$.

This conclude the proof.

$\endgroup$
  • $\begingroup$ Why should we remove isolated vertices other than $\nu_0$ and use two new colors? Could we just remove all edges from $v_0$, and if the new graph $G_1$ has some coloring, get a coloring of $G$ by using new color for $\nu_0$? $\endgroup$ – Fedor Petrov Jul 16 '17 at 9:54
  • $\begingroup$ You are right. But to answer this question, it doesn't really matter for adding finite many numbers, since the chromatic number is infinite. It matters only when the chromatic number is finite, in this case the argument is not true, you can find a graph, for instance $K_{n}$ is a witness, with chromatic number $n$ but all its minors have chromatic number strictly less than $n$. $\endgroup$ – Jiachen Yuan Jul 16 '17 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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