Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number (synonym: connected pseudoachromatic number, cf. [Abrams-Berman 2014, p. 315]) of $G$; that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.

Is there a non-complete graph $G_0$ with at least $3$ vertices and with the following two properties?

  1. whenever you remove a vertex, the chromatic number gets decreased (that is, $G$ is vertex-critical, to use an established term), and
  2. whenever you identify two non-adjacent vertices, $h(\cdot)$ gets increased. (We could call graphs with this property "identification-critical"; I do not know of an established terminology).


[Abrams-Berman 2014] Lowell Abrams, Yosef Berman, ''Connected pseudoachromatic index of complete graphs'', Australasian Journal of Combinatorics, Volume 60(3) (2014), 314-324

  • $\begingroup$ The article you link doesn't define vertex-criticality. $\endgroup$ – Wojowu Dec 29 '17 at 13:40
  • 2
    $\begingroup$ Was the -1 vote due to the bad wording of the original post before the edit, or is there an easy example to what I am asking? $\endgroup$ – Dominic van der Zypen Dec 29 '17 at 15:30
  • $\begingroup$ I suppose you want $G_0$ to have at least $3$ vertices. $\endgroup$ – domotorp Jan 1 '18 at 21:40
  • 1
    $\begingroup$ Dear @ Dominic van der Zypen: under the hypothesis that the leaving out of the usual technical term was not your intention, I proactively added the usual technical term, and a few things more (noted in the log of the edit). This considerably improves the question, by putting it into the proper context within the recent research literature. $\endgroup$ – Peter Heinig Jan 5 '18 at 12:31
  • 1
    $\begingroup$ Thanks @PeterHeinig, your edits and contributions are always very welcome! I will make the changes you mention in your most recent comment. $\endgroup$ – Dominic van der Zypen Jan 5 '18 at 14:16

Your Answer

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

Browse other questions tagged or ask your own question.