حدس دینیتز

در سال ۱۹۷۸ جف دینیتز (Jeff Dinitz) مسئله زیر را در نظریه گراف بیان کرد که به حدس دینیتز مشهور شد:

فرض کنید L مربع از مرتبه n باشد؛ که در هر خانه (i,j) از L لیست (C(i,j از n رنگ مختلف داریم. آیا می‌توان به هر خانه از L یکی از رنگ‌های لیست آن خانه را نسبت داد به‌طوری‌که هر رنگ در هر سطر و در هر ستون حداکثر یک بار ظاهر شود؟

این مسئله در حالتی که همه لیستها برابر با {n،...۳٬۲٬۱} باشند، ساده است، کافیست ۱ تا n را در سطر اول بنویسیم، و در هر سطر دیگر اعداد سطر قبل را یک واحد چرخش دهیم تا یک مربع لاتین چرخشی به دست می‌آید که بوضوح شروط مسئله را ارضا می‌کند.

ولی مسئله همیشه به این سادگی نیست. مربعی ۲*۲ را در نظر بگیرید که

{c (۱٬۱) ={۱٬۲ و {c (۱٬۲) ={۲٬۳ و {c (۲٬۱) ={۱٬۳ و {c (۲٬۲) ={۳٬۲.

اگر کسی خانه (۱٬۱) را با ۱ و خانه (۱٬۲) را با ۲ رنگ کند دیگر نمی‌تواند مربع را کامل کند. چرا که هم‌خانه (۲٬۱) و هم‌خانه (۲٬۲) باید با ۳ رنگ شود.

این مسئله را می‌توان با قرار دادن یک راس در هر خانه مربع و وصل کردن دو راس که در در یک سطر یا یک ستون هستند، به یک مسئله رنگ آمیزی لیستی گراف‌ها تبدیل کرد. گرافی که اینگونه از این مربع به دست آمد را (G(L بنامید.

اکنون به قضیه زیر دربارهٔ عدد رنگی لیستی در گراف‌های جهتدار که توسط Bondy-Boppana-Siegel اثبات شده توجه کنید.

قضیه: اگر (D=(V,E یک گراف جهتدار باشد که به هر راس v از آن یک مجموعه (C(v به عنوان لیست رنگی نسبت دهیم و (C(v بیشتر از درجه خروجی v عضو داشته باشد، و هر زیرگراف القایی راسی از D دارای هسته باشد در این صورت می‌توان هر راس را با یکی از رنگهای لیستش رنگ کرد که هر دو راس مجاور همرنگ نباشند.

در ادامه نیاز به مفهومی به نام تطابق پایدار داریم:

فرض کنید [G[X,Y یک گراف دو بخشی باشد که برای هر راس v از G همسایه‌های راس v یک ترتیب و اولویتی برای v دارند. تطابق M را پایدار گوییم هرگاه برای هر یال uv از G که در M نیست، یا یال uy در M هست که از نظر u, راس y اولویت بیشتری نسبت به v دارد یا یال vx در M هست که از نظر v, راس x اولویت بیشتری نسبت به u دارد.

Gale در سال ۱۹۶۲ ثابت کرد هر گراف دو بخشی یک تطابق پایدار دارد.

اکنون در ادامه اثباتی از (Galvin ۱۹۹۳) ارائه می‌دهیم که نشان می‌دهد پاسخ سؤال مطرح شده توسط Dinitz همواره مثبت است. نشان می‌دهیم (G(L عدد رنگی لیستی n دارد. برای این کار یال‌های (G(L را طوری جهت می‌دهیم که درجه خروجی هر راس برابر n-۱ باشد و هر زیر گراف القایی (G(L دارای هسته باشد. پس بنابر قضیه بالا هر راس v از (G(L را می‌توان با یکی از رنگ‌های لیستش رنگ کرد که با رنگ رأس‌های همسایه (راس‌های هم سطر یا هم ستون) v متفاوت باشد. یعنی هر رنگ در هر سطر یا ستون حد اکثر یکبار ظاهر می‌شود.

فرض کنید خانه‌های L را با اعداد ۳٬۲٬۱،... ، n طوری پر کرده‌ایم که L یک مربع لاتین از مرتبه n شود. عدد نوشته شده در خانهٔ (i,j) این مربع را (L(i,j بنامید. یال‌های (G(L را به شرح زیر جهت دهید:

اگر (L(i,j از (L(i,k کمتر بود جهت یال ((i,j)(i,k)) در (G(L از (i,j) به (i,k) باشد، و اگر (L(i,j از (L(k,j بیشتر بود جهت یال ((i,j)(k,j)) در (G(L از (i,j) به (i,k) باشد،

بدیهیست که درجه خروجی هر راس برابر n-۱ است.

فرض کنید A زیر مجموعه‌ای از رأس‌های (G(L باشد

گراف دو بخشی [H[X,Y را در نظر بگیرید:

X = مجموعه سطرهای L,

Y = مجموعه ستون‌های L,

راس i از X به راس j از Y متصل است اگر (i,j) عضو A باشد،

برای هر i از X، اولویت ستون j از ستون k بیشتر است اگر (L(i,k از (L(i,j کمتر باشد،

برای هر j از Y، اولویت سطر i از سطر k بیشتر است اگر (L(i,j از (L(k,j کمتر باشد،

می‌دانیم هر گراف دو بخشی تطابق پایدار دارد، پس H هم تطابق پایداری مثل M دارد، دقت کنید هر یال M بین راس i از X و j از Y متناظر با راس (i,j) از (G(L است، به راحتی دیده می‌شود رأس‌های متناظر M یک هسته برای زیر گراف القای <A> می‌سازند.

پس ثابت کردیم هر زیر گراف القایی از (G(L هسته دارد، پس حکم ثابت شد.

منابع

• F. Galvin (1995). "The list chromatic index of a bipartite multigraph". Journal of Combinatorial Theory. Series B. 63 (1): 153–158. doi:10.1006/jctb.1995.1011.
• Zeilberger, D. (1996). "The Method of Undetermined Generalization and Specialization Illustrated with Fred Galvin's Amazing Proof of the Dinitz Conjecture". The American mathematical monthly. 103 (3): 233–239. arXiv:math/9506215. Retrieved 2009-04-15. {{cite journal}}: Cite has empty unknown parameters: |coauthors= و |month= (help)
• Chow, T. Y. (1995). "On the Dinitz conjecture and related conjectures". Discrete Math. 145: 145–173. Retrieved 2009-04-15. {{cite journal}}: Cite has empty unknown parameters: |month= و |coauthors= (help)