0
$\begingroup$

This is a follow-up to this question.

Let $G=(V,E)$ be a finite, simple, undirected graph such that every vertex has degree at least $2$. Given $n\in\mathbb{N}$, a map $c:E \to \{1,\ldots, n\}$ is said to be a weak coloring if for every $v\in V$ the edges adjacent to $v$ do not all have the same color. More formally, we want the restriction $c|_{E(v)}$ to be non-constant, where $E(v) = \{e\in E: x\in e\}$. (Is there a name for this kind of edge-coloring?)

Is there some positive integer $n_0\in\mathbb{N}$ such every graph $G=(V,E)$ with minimal degree $2$ has a weak edge coloring $c:E\to\{1,\ldots,n_0\}$? If yes, what is the smallest such integer?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

According to the answers to the previous question, the only connected graphs which require more than two colors are odd cycles, which are trivially weak 3-colorable. Therefore, $n_0 = 3$ always suffices.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yeah sorry, I misread that in the old answers. I assume your argument also shows $n_0 = 3$ for infinite graphs? - Very nice argument! $\endgroup$
    – Dominic van der Zypen
    Commented Nov 4, 2017 at 13:18
  • $\begingroup$ @DominicvanderZypen Euler tour is not universally present in infinite graphs with even degrees. It seems plausible that $n_0 = 3$ holds in infinite case, but I'm not yet sure how to prove it. $\endgroup$
    – Mikhail Tikhomirov
    Commented Nov 4, 2017 at 20:02

You must log in to answer this question.

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