رنگ آميزي ليستي گراف هاي بي نقص بدون پنجه

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

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

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

براي عدد طبيعي k، k-رنگ آميزي رأسي از گراف G كه اين f : V (G) 􀀀! f1; 2; :::; kg عبارت است از نگاشت G -رنگ آميزي رأسي از گراف k ،k براي عدد طبيعي -رنگ پذير k را G رنگ آميزي معتبر است اگر هر دو رأسمجاور با رنگ هاي غيريكسان رنگ آميزي شده باشند. يكگراف ، يك G -رنگ آميزي معتبر باشد. همچنين كم ترين تعداد رنگ هايي را كه لازم است تا گراف k داراي يك G گوييم هرگاه نمايش مي دهيم. (G) مي ناميم و آن را با G -رنگ آميزي معتبر داشته باشد عدد رنگي گراف k نوع ديگري از رنگ آميزي كه براي اولين بار به وسيله ي دانشمندان بزرگي مانند اردوش، رابين و تيلور در سال 1978 ليستي از G از گراف v و ويزينگ در سال 1992 مطرح گرديد، رنگ آميزي ليستي است. فرض مي كنيم براي هر رأس ،v طوري انجام دهيم كه براي هر رأس c داده شده است؛ مي خواهيم يك رنگ آميزي-رأسي به نام L(v) رنگ ها به نام -انتخاب پذير k ،G -رنگ پذير م ي گويند. گراف L ،G . اگر بتوان چنين رنگ آميزي را انجام داد، به گراف c(v) 2 L(v) -رنگ پذير باشد. عدد انتخاب يا عدد L ،G ، v 2 V (G) براي هر jL(v)j = k با شرط L است اگر براي هر ليست ch(G) -انتخاب پذير است و آن را با k ،G گفته مي شود كه گراف k به كوچك ترين عدد طبيعي G رنگي-ليستي گراف نمايش مي دهند. به طور مشابه مي توان نسخه رنگ آميزي يالي و رنگ آميزي ليستي يالي را نيز تعريف كرد و عدد رنگي يالي و عدد ch(G) = (G) نشان مي دهند. در اين پايان نامه قصد داريم تساوي هاي ch ′(G) و ′(G) انتخاب يالي را به ترتيب با را براي گراف ch(G) = (G) مورد بررسي قرار دهيم و به ويژه تساوي G را در هر گراف دلخواه ch ′(G) = ′(G) و كه يك گراف بي نقص بدون پنجه است بررسي خواهيم كرد. G در گراف هاي ويژه، مكمل گراف هاي (G) = !(G) در قسمت اصلي اين پايان نامه نتايج موجود در رابطه با حدس بدون مثلث و مكمل گراف هاي دوبخشي را مرور كرده ايم. سپس نتايج تحقيقات روي گراف هاي بي نقص بدون پنجه كه شده است جمع آوري كرده ايم. نهايتا قضيه !(G) را با 4 G منجر به اثبات حدس براي گراف هاي بي نقص بدون پنجه ساختاري چادنوفسكي و همكاران را براي گراف هاي بي نقصبدون پنجه بررسي كرده ايم و تلاش هايي را براي اثبات حدس رنگ آميزي ليستي با كمك اين قضيه ساختاري انجام داده ايم.

215044

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

رياضي

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

بهناز عمومي

غلامرضا اميدي، غفار رئيسي

رامين جوادي