1- أثبت أن العدد اللوني لبيان يساوي أكبر عدد لوني لمركباته.
2- جد بيانا G بحيث إن G ليس بيانا تاما و لا حلقة فردية، و لكن يوجد ترتيب لرؤوس هذا البيان :
3- بحيث يستخدم التلوين الجشع لهذه الرؤوس بالنسبة إلى هذا الترتيب ∆(G) + 1 لونا.
4- أثبت أن G □ H يتفكك إلى n(G) نسخة من H و n(H) نسخة من G.
5- أثبت أو انقض : يوجد لكل بيان G لوني من الدرجة k تلوين ب k من الألوان بحيث يحوي أحد صفوفه اللونية a(G) رأسا.
6- استخدم النظرية 21.1.5 لإثبات وجود مسار مولد لكل دوري. ([1934]Redei ).
7- حدد عدد الألوان الازم لوضع علامات دالة على V(Kn) بحيث إن كل صف لوني يولد بيانا جزئيا درجته القصوى أقل من k أو يساويها.
8- افترض أن G بيان تتقاطع حلقاته الفردية زوجا زوجا ؛ بمعنى أنه يوجد رأس مشترك بين أي حلقتين فرديتين في G. أثبت أن X(G) ≤ 5.
9- افترض أن كل ضلع لبيان G يظهر في حلقة واحدة على الأكثر. أثبت أن كل قالب في G ضلعا، أو حلقةـ أو رأسا معزولا. استخدم هذا في الإثبات أن X(G) ≤ 3.
10- افترض أن G بيان منتظم من الدرجة 20، له 360 رأسا، و قد تم تكوينه بالطريقة الآتية :
11- وضعت الرؤوس على دائرة بأبعاد متساوية بينهما. تكون الرؤوس المفصولة بدرجة أو بدرجتين غير متجاورة، أما الرؤوس المفصولة بثلاث، أو ربع، أو خمس، أو ست درجات فتكون متجاورة. لا توجد أي معلومات عن التجاورات الأخرى (ما عدا أن البيان منتظم من الدرجة 20). أثبت أن X(G) ≤ 19. (مساعدة : لون الرؤوس المتتابعة بترتيب معين حول الدائرة). (Pritikin).
12- افترض أن g هي بيان مسافة الفصل في المستوى في هذا البيان V(G) = R2، و تكون النقطتان متجاورتين إذا و فقط أذا كانت المسافة التقليدية بينهما تساوي 1 (هذا بيان غير منته). أثبت أن 4 ≤ X(G) ≤ 7. (مساعدة : لبرهان الحد الأعلى، قدم تلوينا صريحا للمناطق آخذا بالحسبان حدود كل منطقة). (هادوايجر، موزر-موزر) ([1961]Hadwiger [1945, 1961], Moser-Moser )
13- افترض أن Sm،....، S1 مجموعات منتهية، و أن xSm...U = S1x. عرف بيانا G رؤوسه عناصر U، حيث u ↔ vإذا و فقط إذا اختلف u عن v في كل إحداثي، جد X(G).
14- افترض أن لديك إشارة ضوئية بتم التحكم فيها عن طريق مفتاحين كهربائيين، بحيث إن كلا منهما يمكن أن يوضع ب n من المواقع، و لكل موقع من هذه المواقع للمفتاح يظهر أحد ال n لونا الممكنة، و عند تغيير موضع المفتاحين يتغير اللون. أثبت أن اللوم الذي يظهر يتحدد من خلال موقع أحد المفتاحين، ثم وضح ذلك بدلالة العدد اللوني لبيان معين. (Greenwell-Lovasz [1974]).
15- أثبت أن نظرية بروكس تكافئ العبارة الآتية : كل بيان منتظم من الدرجة k-1 و حرج من الدرجة Kk يكون بيانا تام أو حلقة فردية (مساعدة : لبرهنة نظرية بروكس من هذه العبارة، خذ في الحسبان بيانا جزئيا حرجا من الدرجة k للبيان المعطى G، حيث إن G لوني من الدرجة k).
16- افترض أن G بيان بسيط له n من الرؤوس، و m من الأضلاع، و درجته القصوى تساوي 3 على الأكثر. افترض أنه لا يوجد ل G أي مركبة تشكل بيانا تاما على أربعة رؤوس. أثبت أن G يحوي بيانا جزئيا ثنائي الفرع عدد أضلاعه يساوي m-2/ 3 على الأقل. (مساعدة " طبق نظرية بروكس. و بعد ذلك، وضح كيف نحذف بعض الأضلاع لتحويل التلوين الثلاثي الفعلي ل G إلى تلوين ثنائي لبيان جزئي كبير من G).
17- أثبت أنه يمكن تلوين بيان بيترسون بلونين، بحيث يتألف البيان الجزئي المستحدث من كل صف لوني من أضلاع و رؤوس معزولة.
18- أثبت أن البيان البسيط يكون بيانا تاما متعدد الفروع إذا و فقط إذا خلا هذا البيان من بيان جزئي مستحدث له ثلاثة رؤوس و ضلع واحد
19- افترض أن G بيان، بحيث إن x(G – x – y) = x(G) – 2 لكل زوج x و y من الرؤوس المختلفة. أثبت أن G بيان تام. (تعليق : لقد خمن لوفاز أن النتيجة كذلك تتحقق عندما نفرض هذا الشرط فقط على الرؤوس المتجاورة).
20- أثبت أن البيان البسيط يكون بيانا تام متعدد الفروع إذا و فقط إذا خلا هذا البيان من بيان جزئي مستحدث له ثلاثة رؤوس و ضلع واحد.
21- حدد أصغر عدد الأضلاع لبيان مترابط له n من الرؤوس، و عدده اللوني يساوي k (مساعدة : خذ في الحسبان البيانات الجزئية الحرجة من الدرجة Ersov-Kozuhin [1962] k، انظر Bhasicer-Samad-West [1994] من أجل درجات الترابط الأعلى.
22- إذا كان لدينا تلوين أمثل لبيان لوني من الدرجة k (عدده اللوني يساوي k)، أثبت أنه يوجد لكل لون i رأس لونه i يجاور رؤوسا ملونة بال k-1 لونا الأخرى.
23- أثبت أنه إذا كان البيان G حرجا لونيا، فإن البيان ׳G المولد من G من خلال بناء مسيلسكس يكون أيضا حرجا لونيا.
24- من بين البيانات البسيطة على n من الرؤوس التي تخلو من عصبة من الدرجة r+1. أثبت أن بيان توران هو البيان الفريد الذي له أكبر عدد من الأضلاع. (مساعدة : تفحص برهان النظرية 9.2.5 بدقة و حذر أكثر).
25- تحصل مدينة دائرية الهيئة قطرها أربعة أميال على 18 محطة تقوية للهواتف المحمولة، و تستطيع كل محطة أن تبث إلى بقية المحطات التي تبعد عنها مسافة أقل أو تساوي ثلاثة أميال. أثبت أن محطتين على الأقل تستطيعان أن تبثا إلى خمس محطات أخرى على الأقل بغض النظر عن كيفية توزيع هذه المحطات في المدينة.
26- افترض أن G بيان يخلو من المخالب (لا يستحدث منه K1,3) : a) أثبت أن البيان الجزئي المستحدث من اتحاد صفين لونيين في أي تلوين فعلي للبيانG يتكون من مسارات و حلقات زوجية. b) أثبت أنه إذا وجد ل G تلوين فعلي يستخدم بالضبط k من الأولان، فإنه يوجد ل G تلوين فعلي من الدرجة k، حيث يختلف حجم الصفوف في هذا التلوين بمقدار 1 على الأكثر، (Niessen-Kind [2000]).
27- افترض أن G بيان حرج من الدرجة 4، و له مجموعة فاصلة s حجمها 4. أثبت أنه يوجد للبيان [S]G أربعة أضلاع على الأكثر، (Pritikin).
28- أثبت أن كل بيان بسيط درجته الصغرى تساوي 3 على الأقل يجب أن يحوي تقسيما ل K4. (مساعدة : أثبت النتيجة الأقوى-كل بيان بسيط غير تافه له على الأكثر رأس واحد درجته أقل من 3 يحوي تقسيما ل K4. يوضح برهان النظرية 20.2.5 أن كل بيان مترابط من الدرجة 3 يحوي تقسيما ل Dirac [1952 a], (K4).
29- افترض أن G بيان لوني من الدرجة k. و لاحظ أن البديهية 18.1.5، و الفرضية 8.1.2 تشير إلى أن G يحوي كل شجرة لها k من الرؤوس بوضفه بيانا جزئيا. قم بتقوية هذه النتيجة لبيان مماثل، وضع عليه علامات دالة : إذا كان ƒ تلوينا فعليا ب k من الألوان للبيان G، و كانت T شجرة رؤوسها : [w1, …, wk]، فتوجد دالة : V(T)→V(G) ϕ تحافظ على التجاور بحيث إن Ƒ(ϕ) (Wi) )=i لكل i. Gyarfas-Szemeredi-Tuza [1980], Summer [1981])
30- افترض أن G بيان لوني من الدرجة k خضره يساوي على الأقل، أثبت أن G يحوي كل شجرة على k من الرؤوس بوصفه بيانا جزئيا مسحدثا، (سومنز، جيرفاس، سنرميردي-توزا) .(Gyarfas-Szemerédi-Tuza [1980], Summer [1981])
31- استخدم التكرار اللوني للحصول على كثيرة الحدود اللونية لكل شجرة على n من الرؤوس.
32- أثبت أن مجموع معاملات X(G ;K) يساوي صفرا، إلا إذا خلا G من الأضلاع (مساعدة : عندما تكون الدالة كثيرة حدود، فكيف يمكن الحصول على مجموع المعاملات ؟).
33- لتكن P بيان بيترسون. من نظرية بروكس، نعلم أن هذا البيان ثلاثي اللون، لذلك، و باستخدام مبدأ طواقي الحمام، نجد في G مجموعة مستقلة S حجمها 4 : a) أثبت أن P – S = 3K2. باستخدام فرع (a) و التماثل، حدد عدد تجزئات رؤوس P إلى ثلاث مجموعات مستقلة. b) بوجه عام، كيف يمكن الحصول على عدد التجزئات إلى أصغر عدد من المجموعات المستقلة من كثيرة الحدود اللونية للبيان G ؟
34- افترض أن العدد اللوني للبيان G يساوي k. أثبت أنه يوجد على الأكثر kn-k تجزئة لرؤوس G إلى k من المجموعات المستقلة، حيث إن البيان الفريد الذي يحقق المساواة هو Kk + (n-k) K1 (عصبة من الدرجة k إضافة إلى n-k رأسا معزولا). (مساعدة : استخدم الاستقراء على n، و خذ في الحسبان حذف رأس واحد)، (Tomescu [1971]).
35- استخدم مبدأ التضمين و الاستبعاد لبرهان النظرية 10.3.5 مباشرة.
36- افترض أن G هو البيان الذي نحصل عليه من K6 من طريق قسمة أحد الأضلاع، استخدم التكرار اللوني لحساب X(G ; k) بوصفه حاصل ضرب لعوامل خطية (عوامل على الشكل k-ci). أثبت أن G ليس بيانا و تريا. (Read [1975], Dmitriev [1980])).
37- افترض أن G بيان وتري. استخدم ترتيب حذف مبسطي لبيان g لبرهنة العبارات الآتية : a) يوجد ل G على الأكثر n من العصب العظمى، حيث تتحقق المساواة في الحالة التي لا يحوي فيها G أضلاعا. (Fulkerson-Gross [1965]). b) إن كل عصبة عظمى في G لا تحوي رأسا مبسطيا للبيان تكون مجموعة فاصلة.
38- افترض أن e ضلع في حلقة C في بيان و تري. أثبت أن e تشكل مثلثا مع رأس ثالث من رؤوس C.
39- افترض أن Q عصبة عظمى في بيان و تري Gـ أثبت أنه إذا كان G – Q بيانا مترابطا، فإن Q تحوي رأسا مبسطيا (Voloshin-Gorgos [1982])
40- افترض أن G بيان فترة، أثبت أن G بيان و تري، و أن Ġ بيان مقارنة.
41- يسمى الضلع في البيان G الذي له توجيه لاحلقي بضلع تابع (غير مستقل) إذا حصلنا على حلقة عندما نعكس اتجاهه : a) أثبت أن كل توجيه لا حلقي لبيان مترابط على n من الرؤوس يحوي n – 1 ضلعا مستقلا. b) أثبت أنه إذا كان X(G) أٌقل من خصر G، فإنه يوجد للبيان G توجيه ليس له أضلاع تابعة. (مساعدة : استخدام التقنية الموجودة في برهنة النظرية 21.1.5).
42- إن العدد a(G) للتوجيهات اللاحلقية للبيان G يحقق العلاقة التكرارية a(G) = a(G-e) + a(G. e) (النظرية 27.3.5 فضلا عن أنه من الواضح أن عدد الأشجار المولدة يحقق العلاقة التكرارية نفسها ؛ هل يكون عدد التوجيهات اللاحلقية لبيان G دائما يساوي عدد الأشجار المولدة ؟ و لماذا ؟
