2
$\begingroup$

Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\ldots,n\} \to V$ for some $n\in\mathbb{N}$ with the following properties:

  1. $r$ is surjective,
  2. $\{r(k), r(k+1)\} \in E$ for all $k \in \{0, \ldots, n-1\}$, and
  3. $r(0) = r(n)$.

An easy inductive argument shows that we can select $n$ such that $n \leq 2|G|$.

Given a roundtrip $r$ and a vertex $v\in V$, we assign a roundtrip coloring $c_{r,v}:V\to\mathbb{N}$ of $G$, starting at $v$ in the following manner.

  1. $c_{r,v}(v) = 1$;
  2. since $r$ is surjective, $v$ appears somewhere on $r$, so take the next point, $v^*$ and if $c_{r,v}(v^*)$ has not been defined yet (which it hasn't in the first iteration), assign to it the smallest positive integer $m$ such that none of those neighbors of $v^*$ that already have been assigned a color, have color $m$;
  3. Repeat Step 2 until all points have been assigned a color.

Set $\chi_{r,v}(G) = \max(\text{im}(c_{r,v}))$ and let $\chi_r(G) = \min\{\chi_{r,v}(G):v \in V\}$ be the roundtrip coloring number with respect to $r$.

Question. Is there a global constant $N_0\in \mathbb{N}$ such that whenever $G$ is a finite connected graph, then $\chi_r(G) \leq \chi(G)+N_0$?

$\endgroup$
  • 2
    $\begingroup$ Do you have an example where you do not have equality of $\chi_r(G)$ and $\chi(G)$? This seems to be greedy coloring restricted to those orderings of the vertices in which the ordering respects adjacency. I would not be surprised if the answer to your question is negative, but I can't think of an example at the moment. $\endgroup$ – Carl-Fredrik Nyberg Brodda Mar 10 at 10:39
  • $\begingroup$ The process has not been well-defined. To which vertex $v$ and to which of its neighbours should we apply Step 2 at a certain moment? $\endgroup$ – Ilya Bogdanov Mar 10 at 12:11
  • 1
    $\begingroup$ That's right, it is greedy coloring applied to a round-trip, and applied repeatedly for all the points $v\in V(G)$ and then taking the minimal resulting greedy chromatic number. Sorry for the bad description, Ilya, and thanks for the correct term @Carl-FredrikNybergBrodda. - I haven't been able to find an example of a connected graph with $\chi_r(G) > \chi(G)$, but there must be - otherwise this would be a polynomial time coloring (which is I think not inconsistent / impossible but it's unlikely this would be one.) $\endgroup$ – Dominic van der Zypen Mar 10 at 16:08
  • $\begingroup$ @DominicvanderZypen I don't see immediately how it would be polynomial time. Surely enumerating all roundtrips is at least exponential, or am I missing something obvious? $\endgroup$ – Carl-Fredrik Nyberg Brodda Mar 11 at 20:33
  • $\begingroup$ @Carl-FredrikNybergBrodda You don't enumerate all round-trips, but pick just one, say $r$, and then you perform the greedy coloring along $r$ for every vertex $v\in V$ $\endgroup$ – Dominic van der Zypen Mar 12 at 10:18
3
$\begingroup$

There are graphs with $\chi(G) = 4$ and arbitrarily large $\chi_r(G)$ (linear in the number of vertices) for a badly chosen roundtrip $r$.

A family of examples can be constructed as follows: For an even integer $n \geq 4$, consider the graph with vertex set $\{v_i,v_i',u_i,u_i'\mid 1 \leq i \leq n\}$ and edges

  • $v_iv_j'$ and $u_iu_j'$ for $i \neq j$,
  • $v_iv_{i+1}$, $v_i'v_{i+1}'$, $u_iu_{i+1}$, and $u_i'u_{i+1}'$ for $1 \leq i < n$, and
  • $v_n'u_1$ and $u_n'v_1$.

In other words, the induced subgraph on the vertices $v_i,v_i'$ is a complete bipartite graph minus a matching plus a spanning path on both sides, and similarly for $u_i,u_i'$, and there are two additional edges connecting these two graphs.

It is easy to see that $\chi (G_n) = 4$: Colour the path spanned by $v_i$ and $u_i'$ with colours 1 and 2 and the path spanned by $u_i$ and $v_i'$ with colours 3 and 4. Fewer colours are not possible because $G_n$ contains copies of $K_4$.

For $\chi_r(G_n)$ consider the roundtrip $r$ given by $$ v_1, v_2, v_1', v_2', v_3, v_4, v_3', v_4', \dots, v_{n-1}, v_n,v_{n-1}', v_n', u_1, u_2, u_1', u_2', u_3, u_4, u_3', u_4', \dots, u_n', v_1. $$

Without loss of generality assume that the chosen starting point $v$ is $u_i$ or $u_i'$, so the vertices $v_i$ and $v_i'$ are visited in order $v_1, v_2, v_1', v_2', v_3, v_4, v_3', v_4', \dots, v_{n-1}, v_n,v_{n-1}', v_n'$. It is not hard to check inductively that

  • $v_1$ and $v_2$ are coloured with colours $\{1,2\}$ (not necessarily in that order),
  • $v_i'$ receives the same colour as $v_i$,
  • for $i \geq 3$, the colour of $v_i$ (and thus also $v_i'$) is $i$.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.