4
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ The article you link doesn't define vertex-criticality. $\endgroup$
    – Wojowu
    Commented Dec 29, 2017 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
    Commented Dec 29, 2017 at 15:30
  • $\begingroup$ I suppose you want $G_0$ to have at least $3$ vertices. $\endgroup$
    – domotorp
    Commented Jan 1, 2018 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
    Commented Jan 5, 2018 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
    Commented Jan 5, 2018 at 14:16

0

Reset to default

You must log in to answer this question.