A special graph coloring problem

253 Views Asked by At

Let $G$ be an undirected graph. We define:

An Orientation $D$ from $G$: A subgraph $D$ with $V(D) = V(G)$ such that for every edge $\{u, v\} \in E(G)$, we take either $(u, v)$ or $(v, u)$ in $D$.

We call a function $c: V(D) \rightarrow \{1, ..., k\}$ a $k$-In-Out-Coloring if for every vertex $v \in V(D)$ the following holds: $$\{c(u) | (u, v) \in E(D) \} \cap \{c(w) | (v, w) \in E(D) \} = \phi$$

In other words, no vertex in a $k$-in-out-colored, directed graph has an in-neighbor $u$ and an out-neighbor $w$, so that $c(u) = c(w)$. In this graph for example, the vertices $0$, and $2$ have to colored in different colors, so $c(0) \neq c(2)$. Note that we didn't impose restrictions on vertex $1$, it is allowed to be colored in $c(0)$ or $c(2)$.

For a function $f: A \rightarrow B$ and a subset $C \subseteq A$ we define a restriction from $f$ onto $C$ as $f_{\restriction C}(x):= f(x)$ if $x \in C$. So the function $f_{\restriction C}$ has the type $f_{\restriction C}: C \rightarrow B.$

Let $k \in \mathbb{N}$ be fixed, $G$ an undirected Graph (with no parallel edges or self-loops) with countably infinite vertices and let $c:V(G) \rightarrow \{1, ..., k\}$ be an $k$-in-out coloring function.

Prove: If every finite subgraph $G'$ from $G$ has an orientation which is $k$-in-out-colored by $c_{\restriction V}(G')$, then there must exist an orientation of $G$, which is $k$-in-out-colored by $c$.

There are too many layers in this proof and I don't know where to begin. A proof by contradiction seems suitable but even then, I don't see what follows.

If every subgraph $G'$ has an orientation which is $k$-in-out-colorable by $c_{\restriction V}(G')$, then the subgraph $H$ with $V(H) = V(G)$ and $E(H) = E(G)$ is $k$-in-out-colorable by $c_{\restriction V}(G')$. If $H$ is $k$-in-out-colorable by this restriction function, then it must be colorable by $c$, and so must be $G$, which is exactly the same graph as $H$. So I'm not really sure what the question is looking for. Any help would be much appreciated.

1

There are 1 best solutions below

1
On

As the vertex set is enumerable, so does the set of edges. Let $\{e_{i}\}_{i \in \mathbb{N}}$ be an enumeration of $E(G)$. For each $i \in \mathbb{N}$, let $e_{i}=\{u_{i},v_{i}\}$ and define $$G_{i} = \left(\{u_1,v_1,\ldots,v_i,u_i\}\bigcup_{j = 1}^i e_{i}, \{ e_{j} ~\colon j \in \{1,\ldots, i\}\})\right).$$ In other words, $G_{i}$ is the finite graph induced by the edges $\{e_{1},\ldots, e_{i}\}$. Let $G_{i}'$ be the orientation of $G_{i}$ having a $k$-in-out-coloring.

We define an orientation in $\{e_{i}\}_{i \in \mathbb{N}}$ by induction. First, we have two ways to orientate the edge $e_{1}$, $(u_{1},v_{1})$ or $(v_{1},u_{1})$. As we have two orientations of $e_1$ appearing in an infinity number of digraphs $G_i'$, then, by the pigeonhole principle, at least one of theses orientations occurs in an infinite subsequence of $\{G_{i}'\}$. We define $\overrightarrow{e_{1}}$ to be a orientation of $e_{1}$ occurring in a infinity number of the orientations $\{G_{i}'\}$; let $\{G_{i_{k}}'\}_{k \in \mathbb{N}}$ be the subsequence where such orientation occurss. Now, using the argument, notice that some orientation of $e_{2}$ occurs in an infinite number of orientations of $\{G_{i_{k}}\}$. Then, taking a subsequence of $\{G_{i_{k}}\}$, we find infinitely many indexes $j_1,j_2,\ldots$, such that in all digraphs $\{G_{j_k}\}_{k \in \mathbb{N}}$, the orientation of $e_1$ is $\overrightarrow{e_{1}}$, and the orientation of $e_2$ is fixed as well, denote it by $\overrightarrow{e_{2}}$.

In this way, for each $i \in \mathbb{N}$, we can define a orientation $\overrightarrow{e_{i}}$. Then, $A=\{\overrightarrow{e_{1}},\overrightarrow{e_{2}},\ldots\}$ is a orientation of $G$.

We must prove that $A$ respects the property, i.e., for the coloring given in hypothesis, every direct path $(w_1,z,w_2)$ is such that $c(w_1)\neq c(w_2)$. Suppose otherwise, take two vertices $w_{1}$ and $w_{2}$ such that $c(w_{1}) = c(w_{2})$ and $(w_1,z,w_2)$ is a directed path in $(V(G),A)$. Let $i_{1}$ and $i_{2}$ be natural numbers such that $(w_{1}, z) = \overrightarrow{e_{i_1}}$ and $(z,w_{2}) = \overrightarrow{e_{i_{2}}}$. Without loss of generality suppose that $i_{2} > i_{1}$.

Using our construction, we know that there is a subsequence $\{G_{j_k}'\}_{k \in \mathbb{N}}$ where the orientations of $e_1,\ldots,e_{i_2}$ are constant and equal to $\overrightarrow{e_{1}},\ldots,\overrightarrow{e_{i_2}}$. Let $G^*$ be an arbitrary graph in this subsequence of orientations. As $(w_{1},z,w_{2})$ is a directed path in $G^*$ and the property holds in the finite case(by hypothesis), we have that $c(w_{1}) \neq c(w_{2})$. A contradiction.

I know that it is far from being easy to understand this demonstration and maybe its because of my english mistakes, I am sorry in advance. If you don't understand, feel free to ask.