Questions tagged [graph-minors]

A graph $H$ is called a minor of a graph $G$ if $H$ can be obtained from $G$ by contracting edges, deleting edges, and deleting isolated vertices.

Filter by
Sorted by
Tagged with
46 votes
8 answers
5k views

Can a problem be simultaneously polynomial time and undecidable?

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums. The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
Gordon Royle's user avatar
  • 12.3k
2 votes
3 answers
290 views

Hadwiger number and minimal degree

Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. If $\delta(G)$ is the minimal degree of $G$, do we have $\delta(G)\leq\eta(G)$?
Dominic van der Zypen's user avatar
26 votes
0 answers
648 views

Planar minor graphs

The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one. Apparently, it came as a generalization of ...
Pierre Dehornoy's user avatar
5 votes
0 answers
93 views

Increasing the Hadwiger number by identifying non-adjacent points

This is a specialization of a more general, still unanswered question. Suppose $G$ is a finite, simple graph. Let $h(G)$ denote the Hadwiger number, that is, the maximum $n\in\mathbb{N}$ such that $...
Dominic van der Zypen's user avatar
4 votes
2 answers
454 views

Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge. Note that the number of cycles in $k$-necklace is at least $2^k.$ Question : Suppose a ...
Raghav Kulkarni's user avatar
4 votes
0 answers
218 views

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}$ ...
Dominic van der Zypen's user avatar
4 votes
1 answer
303 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let $G$...
Raghav Kulkarni's user avatar
0 votes
1 answer
118 views

Complete minors of the grid graphs $\mathbb{Z}^n$

Let $n>1$ be an integer. We say that two points $(x_1,\ldots,x_n),(y_1,\ldots,y_n)\in\mathbb{Z}^n$ are a member of the edge set $E_n$ if and only if $$\sum_{i=1}^n|x_i-y_i| = 1.$$ Question. Given ...
Dominic van der Zypen's user avatar
0 votes
1 answer
131 views

Large complete minors of $\mathbb{Z}^\omega$

Let $x,y\in \mathbb{Z}^\omega$ and let $x,y\in\mathbb{Z}^\omega$ form an edge if there is $i\in\omega$ such that $|x_i - y_i|=1$ and $ x_k = y_k$ for all $k\in \omega\setminus\{i\}$. $K_\omega$, the ...
Dominic van der Zypen's user avatar
-2 votes
1 answer
131 views

Identifying two non-adjacent vertices and the effect on the Hadwiger number [closed]

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. What is an example of a graph $G_0=(V_0, ...
Dominic van der Zypen's user avatar