MAX-CUT: вероятностное округление/Задачи/eupce-6-19 — различия между версиями

Версия 20:29, 17 декабря 2024

Задача зарезервирована: Trifonov.dv 19:17, 15 декабря 2024 (UTC)

@@ Строка 1: / Строка 1: @@
 {{проверено|}}
 {{bonus}}
-[[File:eupce-6-19_2023-05-19_12-22-45_image0.png|480px]]
-[[File:eupce-6-19_2023-05-19_12-23-03_image0.png|480px]]
+<latex>
+Let G = (V, E) be an undirected graph and suppose each $v \in V$ is
+associated with a set S(v) of $8r$ colors, where $r \geq 1$.
+Suppose, in addition, that for each $v \in V$ and $c \in S(V)$
+there are at most $r$ neighbors $u$ of $v$ such that $c$ lies in $S(u)$.
+Prove that there is a proper coloring of $G$ assigning to each vertex $v$ a color from its class $S(v)$ such that, for any edge $(u,v) \in E$, the colors assigned to $u$ and $v$ are different.
+You may want to let $A_{u,v,c}$ be the event that $u$ and $v$ are both colored with color $c$ and then consider the family of such events.
+</latex>
+<!-- [[File:eupce-6-19_2023-05-19_12-22-45_image0.png|480px]]
+[[File:eupce-6-19_2023-05-19_12-23-03_image0.png|480px]] -->
 {{reserve-task|[[Участник:Trifonov.dv|Trifonov.dv]] 19:17, 15 декабря 2024 (UTC)}}
 [[Категория:Теоретические задачи]]