توصيفگر ها :
رنگ‌آميزي ناقص , گراف‌هاي تام , هم‌گراف , گراف شكافنده , زيرگراف ممنوعه
چكيده فارسي :
چكيده:
رنگ آميزي ‑ 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
واژگان كليدي: رنگ آميزي ناقص، گراف هاي تام، هم گراف، گراف شكافنده، زيرگراف ممنوعه.
چكيده انگليسي :
This master thesis is based on the following papers
In defective coloring a graph G and two integers k, d are given and it is asked if there is a k-coloring for G such that
the maximum degree induced by any color class is at most d. In this thesis, we study the issue of defective coloring
and while reviewing the available results in this field, we investigate the details of the above article’s results. In the
first article, it is shown that this natural generalization of coloring is much harder on several basic graph classes. In
particular, this problem is NP-hard on split graphs, even when one of the two parameters k, d is set to the smallest
possible fixed value that does not trivialize the problem (d = 2 or k = 1). A simple tree-width based dynamic
programming algorithm is also presented which, together with the aforementioned hardness for split graphs, also
completely determines the complexity of the problem on chordal graphs. Then about the case of co graphs it is shown
somewhat surprisingly, defective coloring turns out to be one of the few natural problems which are NP-hard on this
class. This negative result is completed by showing that defective coloring is in P for co graphs if either k or d is
fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for co graphs when
both k and d are unbounded.
Archdeacon (1987), proved that graphs embedable on a fixed surface can be 3-colored so that each color class
induces a sub graph of bounded maximum degree. Edwards et al. (2015), proved that graphs with no Kt+1-minor
can be t-colored so that each color class induces a sub graph of bounded maximum degree. In the second article, a
common generalization of these theorems is proved with a weaker assumption about excluded sub graphs. This result
leads to new defective coloring results for several graph classes, including graphs with linear crossing number, graphs
with given thickness (with relevance to the earth-moon problem), graphs with given stack- or queue-number.
