رنگ‌آميزي ناقص گراف‌ها

اصفهان : دانشگاه صنعتي اصفهان

رياضي كاربردي

كارشناسي ارشد

چكيده: رنگ آميزي ‑ k يك ،G داده شده و پرسيده مي شود كه آيا براي d و k و دو عدد صحيح G در رنگ آميزي ناقص، يكگراف القا كند. در اين پايان نامه نشان داده مي شود كه اين تعميم ،d وجود دارد به طوري كه هر كلاس رنگ، گرافي با حداكثر درجه طبيعي رنگ آميزي، در چندين كلاس گراف پايه، بسيار سخت است. به طور خاص، اين مسئله روي گراف هاي شكافنده روي كوچك ترين مقدار ثابت ممكن با شرط بديهي نشدن d يا k سخت است، حتي زماني كه يكي از دو پارامتر ‑N P كوچك باشند، ارائه داده d و k مسئله تنظيم مي شود. همچنين يك الگوريتم برنامه نويسي پويا مبتني بر عرضدرختي وقتي مي شود كه همراه با سختي ذكر شده براي گراف هاي شكافنده، پيچيدگي مسئله را در گراف هاي وتري نيز به طور كامل تعيين مي كند. درمورد هم گراف ها، نشان داده مي شود كه به طرز شگفت انگيزي، رنگ آميزي ناقص يكي از معدود مسائل طبيعي يا k سخت است. در ادامه اين نتيجه منفي با نشان دادن اين مطلب تكميل مي شود كه اگر ‑N P است كه در اين كلاس است. همچنين اين مسئله بر روي گراف هاي تام بديهي P ثابت باشد، پيچيدگي مسئله رنگ آميزي ناقص ه مگراف ها d هر دو نامحدود هستند، اين مسئله يك الگوريتم زمان زيرنمايي را براي ه مگراف ها d و k است. همچنين زماني كه P مي پذيرد. آرچديكن در سال 1987 ، ثابت كرد كه گراف هاي نشاندني روي يك سطح ثابت مي توانند 3‑رنگي باشند به طوري كه هر كلاس رنگي يك زيرگراف با حداكثر درجه محدود القا كند. ادواردز و همكاران در سال 2015 ، ثابت كردند كه رنگ، رنگ كرد به طوري كه هر كلاس رنگي يك زيرگراف با حداكثر درجه t را مي توان با Kt+ گراف هاي فاقد ماينور 1 محدود القا كند. در اين پايان نامه يك تعميم رايج از اين قضايا با يك فرضضعيف تر در مورد زيرگراف هاي ممنوعه اثبات شده است. اين نتيجه منجر به نتايج جديد براي رنگ آميزي ناقص چندين كلاس گراف مي شود، از جمله گراف هايي با عدد تلاقي خطي، گراف هايي با ضخامت داده شده (مرتبط با مسئله زمين‑ماه)، گراف هايي با شماره پشته يا صف داده شده. 05Ⅽ رده بندي موضوعي: 15 واژگان كليدي: رنگ آميزي ناقص، گراف هاي تام، هم گراف، گراف شكافنده، زيرگراف ممنوعه.

222505

گراف و تركيبيات

رياضي

دانشگاه صنعتي اصفهان