1
$\begingroup$

Let $H, G$ be finite undirected graphs. We say that $H$ is $r$-degenerate if there exists an ordering of the vertices of $H$ such that the back degree of every vertex is at most $r$. This is equivalent to saying that the minimum degree of any subgraph of $H$ is at most $r$. Let $r(H)$ be the degeneracy of $H$.

Say $\phi: H \rightarrow G$ is a graph homomorphism.If $\phi$ is edge-surjective, i.e. for every $uv \in E(G)$ there is an $x, y \in H$ such that $xy \in E(H)$, and $\phi(x) = u$ and $\phi(y) = v$, can we say that $r(H) \geq r(G)$?

Note that in general, we can say nothing, as embedding $H$ into a clique on $v(H) + 1$ vertices increases the degeneracy, and there are graphs of arbitrarily high degeneracy, say $K_{r,r}$ such that they have chromatic number two.

$\endgroup$

1 Answer 1

2
$\begingroup$

No, any connected graph $G$ will have an edge-surjective homomorphism from a long enough path (a homomorphism from a path is the same as a walk, and of course there is a walk that hits all edges if the graph is connected), and a path has degeneracy 1.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .