1. קלט: גרף פשוט G=(V,E). מטרה: לחלק את V לשלוש קבוצות S 1,S 2,S 3, כך שמספר קשתות G שקצותיהן בקבוצות שונות יה…

קלט: גרף פשוט $G=(V,E)$.
מטרה: לחלק את $V$ לשלוש קבוצות $S_1,S_2,S_3$, כך שמספר קשתות $G$ שקצותיהן בקבוצות שונות יהיה מרבי.
הוכיחו שקיים אלגוריתם פולינומי בעל יחס קירוב $2/3$.

נניח שקיים אלגוריתם פולינומי אשר, בהינתן גרף $3$-צביע מדרגה מרבית $\Delta$, מוצא צביעה חוקית ב-$O(\Delta^{1/3})$ צבעים. השתמשו בו כדי להראות שקיים אלגוריתם פולינומי אשר, בהינתן גרף $3$-צביע בעל $n$ קודקודים, מוצא צביעה חוקית ב-$O(n^{1/4})$ צבעים.