Skip to main content
SUPERVISOR
Ramin Gavadi jourtani,Behnaz Omoomi
رامین جوادی جورتانی (استاد مشاور) بهناز عمومی (استاد راهنما)
 
STUDENT
Azam Naghizadeh ghahderijani
اعظم نقی زاده قهدریجانی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1391

TITLE

Equitable List Coloring of Graphs
A proper vertex coloring of graph G , is an assignment of colors to the vertices of G such that, no two adjacent vertices receive the same color. A list assignment L for a graph G assigns to each vertex v ? V ( G ) a set L ( v ) of allowable colors. An L -coloring of G is a proper vertex coloring such that for every v 2 V ( G ) the color on v belongs to L ( v ). For example, when colors represent time periods and vertices are jobs, the list model incorporates restrictions that not all time periods are suitable for all jobs. A list assignment L for G is k -uniform if j L ( v ) j = k for all v 2 V ( G ). A proper vertex coloring of a graph is m -bounded if each color appears on at most m vertices. Given a k -uniform list assignment L for an n -vertex graph G , we say that G is equitably L -colorable if G has an ? n/k ?-bounded L coloring. A graph G is equitably list k -colorable or equitably k -choosable if G is equitably L -colorable whenever L is a k -uniform list assignment for G . Kostochka, et al. 2003, introduced equitable list coloring. Kostochka et al. 2003, proved that, if G is a graph and k ? max { ?( G ) , n ( G ), then G is equitably k -choosable unless G contains K k +1 or is K k;k (with k odd in the latter case). They expressed the following conjecture. Conjecture: Every graph G is equitably k -choosable, whenever k ?( G ). Kostochka et al. 2013, proved that this conjecture yields for ? ? 7 and show that every graph with maximum degree at most r and at least r 3 vertices is equitably ( r +2)-choosable. These results are studied in Chapter 2. Kostochka et al. 2003, proved that a graph G is equitably k -choosable if G is a connected interval graph and k ? ?( G ), or G is a 2-degenerate graph and k ? max { ?( G ) ; 5}. Pelsmajer 2003, proved that every graph G is equitably k -choosable for any k _ ?( G )(?( G ) - 1)/2+ 2. He proved that this conjecture yields for ? ? 3. These results are studied in Chapter 3. Pelsmajer 2008, proved this conjecture for graphs of treewidth w ? 5 if also k ? 3 w - 1. He also show that if G has treewidth w ? 5, then G is equitably k -choosable for k ? max { ?( G ), - 3 w - 1 } . As a corollary, if G is chordal, then G is equitably k -choosable for k ? 3?( G ) - 4 when ?( G ) 2. Xin Zhang and Jian-Liang Wu 2011, proved that every series–parallel graph with maximum degree ? is equitably k -choosable whenever k ? max { ?( G ) ; 3}. These results are studied in Chapter 4. Qiong Li and Yuehua Bu 2009, proved this Conjecture for planar graphs with ?( G ) ? 6 and no 4 or 6-cycles. Junlei Zhu and Yuehua Bu 2010, proved that outerplaner graphs are equitably k -choosable, whenever k ? ?( G ). Aijun Dong et al. 2012, proved that if G is a planar graph without 5 and 7-cycles, then G is equitably k -choosable and equitably k -colorable, where k _ max f ?( G ) , 7 } . Aijun Dong et al. 2013, proved that every planar graph G without 4-cycles is equitably k -choosable, where k _ max { ?( G ) , 7 } . Junlei Zhu and Yuehua Bu 2015, proved that every planar graph G is equitably k -choosable if one of the following conditions holds: (1) G is triangle-free and k _ max f ?( G ) ; 8 g . (2) G has no 4- and 5-cycles and k ? max { ?( G ) , 7 } . These results are studied in Chapter 5.
فرض کنید G یک گراف متناهی، غیرجهت‌دار و ساده با مجموعه رئوس V ( G ) و مجموعه یال‌های E ( G ) باشد. یک k -رنگ‌آمیزی رأسی مجاز از گراف G ، یعنی تخصیص k رنگ به رئوس G به گونه‌ای که رأس‌های مجاور هم رنگ نباشند. یک رنگ‌آمیزی لیستی تعمیمی از مفهوم رنگ‌آمیزی معمولی است، به این ترتیب که به هر یک از اجزای گراف، مجموعه‌ی دلخواه از رنگ‌ها نسبت داده می‌شود و برای رنگ‌آمیزی هر جزء باید از رنگ لیست متناظر آن استفاده شود و یک رنگ‌آمیزی مجاز برای گراف به‌دست آید. لیست تخصیصی L برای گراف G ، k -یکنواخت است اگر برای هر v ? V ( G ) داشته باشیم |L ( v ) | = k ، که در آن L ( v ) لیست رنگ‌های اختصاص داده شده به v است. یک گراف k -انتخاب‌پذیر گفته می‌شود هر گاه برای هر لیست k -یکنواخت داده شده، حداقل یک رنگ‌آمیزی لیستی داشته باشد. در یک رنگ‌آمیزی لیستی اگر همه لیست‌ها از اندازه k باشند و هر رنگ در حداکثر ? n ( G )/k ?از رأس‌ها ظاهر شود، آن‌گاه رنگ‌ آمیزی لیستی منصفانه نامیده می‌شود. یک گراف k -انتخاب‌پذیر منصفانه گفته می‌شود اگر برای هر لیست k -یکنواخت داده شده، حداقل یک رنگ‌آمیزی لیستی منصفانه داشته باشد. رنگ‌آمیزی لیستی منصفانه اولین بار در سال 2003 توسط کاستاچکا و دیگران مطرح شد. در این پایان‌نامه به مطالعه مفهوم k -انتخاب‌پذیر منصفانه برای کلاس‌های خاص از گراف‌ها از جمله جنگل‌ها، گراف‌های بازه‌ای، گراف‌های با تباهندگی کم، گراف‌های سری-موازی، گراف‌های مسطح، گراف‌های مسطح بیرونی و رنگ‌آمیزی لیستی منصفانه و عرض درختی گراف‌ها می‌پردازیم.

ارتقاء امنیت وب با وف بومی