16589

1783 دكتري

دكتري

نظريه گراف و تركيبيات

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

1399

دوازده، 93: مصور

بهناز عمومي

الهام روشن‌بين

امير دانشگر، غلامرضا اميدي، علي طاهرخاني

1400/06/20

كتابنامه

رياضي محض

رياضي

1400/06/20

2692213

به‌دليل جذابيت‌هاي كاربردي و تحقيقاتي انواع رنگ‌آميزي‌هاي گراف، تاكنون تعميم‌هاي گوناگوني از رنگ‌آميزي يالي تعريف شده و مورد بررسي قرار گرفته است. يكي از اين تعميم‌ها به‌نام رنگ‌آميزي يالي ستاره‌اي محتواي اصلي اين رساله را تشكيل مي‌دهد. در رنگ‌آميزي يالي ستار‌ه‌اي، يال‌هاي گراف به‌گونه‌اي رنگ مي‌شوند كه هيچ دو يال مجاوري هم‌رنگ نباشند و همچنين هيچ دور يا مسير دو رنگي به‌طول چهار ايجاد نشود. كمترين تعداد رنگ مورد نياز براي رنگ‌آميزي يالي ستاره‌اي گراف G، عدد رنگي يالي ستاره‌اي گراف ناميده و با نمادχ_s^ʹ (G) نمايش داده‌ مي‌شود. اين مفهوم اولين بار در سال 2008 توسط دنگ و همكارانش مطرح شد. اولين مسأله‌اي كه همواره پس از تعريف يك رنگ‌آميزي مطرح مي‌شود، پيدا كردن مقدار عدد رنگي آن و پيچيدگي محاسباتي آن براي انواع گراف‌ها است. در سال 2018، لي و همكارانش NP-كامل بودن تشخيص درستي نامساوي χ_s^ʹ (G)≤3 براي هر گراف دلخواه G را اثبات كردند. به‌نظر مي‌رسد كه محاسبه عدد رنگي يالي ستاره‌اي‌ حتي براي گراف‌هاي كامل و گراف‌هاي با ماكزيمم درجه سه نيز مسئله‌اي NP-كامل باشد. بنابراين، محاسبه پارامتر عدد رنگي يالي ستاره‌اي گراف‌ها، بررسي پيچيدگي محاسباتي اين مسأله و يا يافتن كران‌هاي عدد رنگي يالي ستاره‌اي براي كلاس‌هاي خاصي از گراف‌ها از نظر تحقيقاتي اهميت دارد. به‌همين منظور، در اين رساله ابتدا عدد رنگي يالي ستاره‌اي درخت‌ها را به‌عنوان يكي از كلاس‌هاي مهم گراف‌ها مطالعه و يك الگوريتم زمان چندجمله‌اي براي تعيين مقدار دقيق آن ارائه مي‌كنيم. محاسبه مقدار عدد رنگي يالي ستاره‌اي گراف‌هاي مسطح بيروني، يكي ديگر از مسائلي است كه مورد توجه قرار گرفته است. در سال 2016، بزگوا و همكارانش حدس زدند كه براي گراف‌ مسطح بيروني G با ماكزيمم درجه ∆، داريم ⌊3Δ/2⌋+1. در اين راستا و به كمك يك الگوريتم زمان ‌چندجمله‌اي، اين حدس را براي خانواده بزرگي از گراف‌هاي مسطح بيروني به ‌نام كاكتوس‌ها ثابت مي‌كنيم. در كاكتوس‌ها هر يال متعلق به حداكثر يك دور است. همچنين، در اين رساله كران‌هاي بالاي تيزي را براي عدد رنگي يالي ستاره‌اي حاصل‌ضرب‌ دكارتي دو گراف دلخواه ارائه مي‌كنيم و سپس به‌طور خاص به مطالعه عدد رنگي يالي ستاره‌اي شبكه‌ها (حاصل‌ضرب دكارتي مسيرها) و شبكه‌هاي توري (حاصل‌ضرب دكارتي دورها) مي‌پردازيم.

Due to the practical and research attractiveness of different types of graph coloring, various generalizations of edge coloring have been introduced and investigated. One of these generalizations, called star edge coloring, is the main subject of this thesis. Star edge coloring is an edge coloring of a graph such that no two adjacent edges are assigned the same color, and every path or cycle of length four receives at least three different colors. The minimum number of colors for which G admits a star edge coloring is called the star chromatic index of G and is denoted by χ_s^ʹ (G). This concept was first introduced by Deng et al. in 2008. The first question that always arises after defining a coloring is finding the value of its chromatic number and its computational complexity for different families of graphs. In 2018, Lei et al. proved that it is NP-complete to determine whether χ_s^ʹ (G)≤3 for an arbitrary graph G. It seems that the star chromatic index is an NP-complete problem to compute, even for complete graphs and graphs with a maximum degree three. Therefore, calculating the star chromatic index of graphs, studying the computational complexity of this problem, or finding the bounds for the star chromatic index of specific classes of graphs is important. For this purpose, in this thesis, we first study the star chromatic index of trees as one of the most important classes of graphs and present a polynomial-time algorithm to determine its exact value. The star chromatic index of the outerplanar graphs is another problem that has been studied. In 2016, Bezgova et al. conjectured that for every outerplanar graph G with maximum degree ∆, we have χ_s^ʹ (G)≤⌊3∆/2⌋+1. Using a polynomial-time algorithm, we prove this conjecture for a large family of outerplanar graphs called Cactus, wherein every edge belongs to at most one cycle. In this thesis, we also present some tight upper bounds for the star chromatic index of the Cartesian product of two arbitrary graphs. We then specifically study the star chromatic index of grids (the Cartesian product of paths) and toroidal grids (the Cartesian product of cycles).

بهناز عمومي

الهام روشن‌بين

امير دانشگر، غلامرضا اميدي، علي طاهرخاني