# Two types of criticality

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).

References

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

• The article you link doesn't define vertex-criticality. – Wojowu Dec 29 '17 at 13:40
• 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? – Dominic van der Zypen Dec 29 '17 at 15:30
• I suppose you want $G_0$ to have at least $3$ vertices. – domotorp Jan 1 '18 at 21:40
• 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. – Peter Heinig Jan 5 '18 at 12:31
• Thanks @PeterHeinig, your edits and contributions are always very welcome! I will make the changes you mention in your most recent comment. – Dominic van der Zypen Jan 5 '18 at 14:16