Sí, $\DeclareMathOperator{In}{In}$ esto parece ser cierto. Sea $\deg^-(v)$ el grado de entrada de $v$ y sea $V$ el conjunto de vértices. Podemos particionar $V$ como $V_f\cup V_<\cup V_{\geq}$ donde:
- $V_f$ es el conjunto de vértices $v$ con grado de entrada finito
- $V_<$ es el conjunto de vértices $v$ con grado de entrada infinito y $|\{u\in \In(v)\mid \deg^-(u)<\deg^-(v)\}|=\deg^-(v)$
- $V_{\geq}$ es el conjunto de vértices que no están en los dos conjuntos anteriores
La idea es entonces intentar encontrar una coloración mayoritaria en el conjunto $$C=\{c:V\to\{1,2,3,4\}\mid c(V_<)\subseteq\{1,2\}\text{ y }c(V_\geq)\subseteq\{3,4\}\}.$$
Para colorear $V_f$ podemos aplicar el principio de compacidad / selección de Rado similar al teorema de de Bruijn–Erdős, para reducir a la siguiente afirmación sobre digrafos finitos.
Dado un digrafo finito con algunas fuentes "adversarias" etiquetadas como $\{1,2\}$ o $\{3,4\},$ existe una coloración $c$ de los vértices no adversarios tal que para cada extensión de $c$ a una coloración $c'$ de todo el conjunto de vértices tal que $c'(v)\in S$ para cada fuente adversaria $v$ etiquetada con $S,$ la coloración $c$ es una coloración mayoritaria.
Prueba: Esta es una ligera variante del argumento en "Coloraciones Mayoritarias de Digrafos". Ordena los vértices de cualquier manera tal que los vértices adversarios vayan después de los vértices no adversarios. Continúa de izquierda a derecha coloreando los vértices no adversarios "$\{1,3\}$" o "$\{2,4\}$" asegurando que $v$ no reciba el mismo color que la mayoría de los vértices en $\In(v)$ a la izquierda de $v.$ Continúa de derecha a izquierda coloreando los vértices no adversarios "$\{1,2\}$" o "$\{3,4\}$" asegurando que $v$ no reciba el mismo color que la mayoría de los vértices en $\In(v)$ a la derecha de $v,$ incluyendo las etiquetas de los vértices adversarios. Combinar estos dos colores da un valor en $\{1,2,3,4\}$ en cada vértice no adversario que cumple con los requisitos. $\Box$
Sea $P$ el conjunto de pares $(U,c)$ con $V_f\subseteq U\subseteq V$ y $c:U\to\{1,2,3,4\}$ tal que cada extensión de $c$ a $c'\in C$ cumple con la condición de coloración mayoritaria en $v$ para cada $v\in U.$ Por el argumento anterior y la compacidad, existe un par maximal $(V_f,c)\in P.$ El conjunto $P$ es completo en cadenas con el ordenamiento de funciones parciales, $(U,c)\leq (U',c')$ si $U\subseteq U'$ y $c'|_U=c.$ Por el lema de Zorn, existe un par maximal $(U,c)\in P.$
Supongamos que $V_<\setminus U$ no es vacío. Escoge un elemento $v$ de grado de entrada mínimo. Todos los $\deg^-(v)$ vértices en $\{u\in \In(v)\mid \deg^-(u)<\deg^-(v)\}$ están en $U\cup V_\geq.$ Así que sabemos que en cualquier coloración en $C$ que extienda $c,$ cada uno de estos vértices será coloreado ya sea con $1$ o $2$ o con algo en $\{3,4\},$ aunque no sea necesariamente determinado cuáles son 3 y cuáles son 4. Sin embargo, podemos elegir ya sea $1$ o $2$ que no coincida con la mayoría de los vértices en $\In(v).$ Extender $c$ con esta elección de $c(v)$ produce una coloración más grande contradiciendo la maximalidad.
Por un argumento similar, para todos los $v\in V\setminus U$ hay menos de $\deg^-(v)$ vértices de $\In(v)$ en $U.$ Esto significa que $(U,c)$ es irrelevante al colorear vértices que no están en $U.$
Supongamos que existe $v\in V\setminus U\subseteq V_\geq.$ Sea $W$ el conjunto de todos los vértices $w\in V\setminus U$ tal que haya un camino dirigido desde $w$ hasta $v,$ a través de vértices en $V\setminus U.$ Intentaremos encontrar una coloración $\hat{c}:W\to\{3,4\}$ tal que $|\hat{c}^{-1}(\{k\})\cap\In(w)|=\deg^-(w)$ para cada $k\in\{3,4\}$ y $w\in W.$ Sea $W_\kappa=\{w\in W\mid \deg^-(w)= \kappa\}$ para cada cardinal $\kappa\geq \deg^-(v).$ El subdigrafo inducido en $\bigcup_{\lambda\leq\kappa}W_\lambda$ tiene todos los grados de entrada a lo sumo $\kappa,$ y cada vértice tiene un camino dirigido hacia el destino $v.$ Por lo tanto $|W_\kappa|\leq \kappa.$ Así que $\{\In(w)\cap W\mid w\in W_\kappa\}$ es una familia de a lo sumo $\kappa$ conjuntos de orden $\kappa.$ Para cada $\kappa$ tal que $W_\kappa\neq\emptyset,$ comenzando con el más pequeño, por inducción transfinita podemos colorear $\bigcup\{\In(w)\cap W\mid w\in W_\kappa\}$ usando colores en $\{3,4\}$ tal que $|\hat{c}^{-1}(\{k\})\cap\In(w)|=\kappa$ para $w\in W_\kappa$ - simplemente usa una biyección $\kappa\to W_\kappa\times\kappa$ para asegurarte de que en cada paso menos de $\kappa$ vértices ya estén coloreados.
Esto muestra que un elemento maximal de $P$ realmente colorea todo el conjunto de vértices.
