Skip to main content
SUPERVISOR
Behnaz Omoomi,Ramin Gavadi jourtani
بهناز عمومی (استاد راهنما) رامین جوادی جورتانی (استاد مشاور)
 
STUDENT
Fatemeh Kiani
فاطمه کیانی

FACULTY - DEPARTMENT

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

TITLE

Equitable Coloring of Graphs
If the vertices of a graph G are colored with k colors such that no adjacent vertices receive the same color and the sizes of any two color stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600" is said to be equitably k -colorable. The equitable chromatic number ?(G) is the smallest integer k such that G is equitably k-colorable. The notion of an equitable coloring was ?rst introduced by W. Meyer. The Equitable Coloring Conjecture (E CC) : Let be a connected graph. If G is neither a complete graph nor an odd cycle , then . The Equitable ? -Coloring Conjecture (E? CC) : A connected graph is equitably ? -colorable if G is different from , and for all . It is also immediate to see that the E ? CC implies the ECC. In C hapter 2 positive evidence for the important equitable ?- coloring conjecture is supplied from graph justify; MARGIN: 0cm 0cm 0pt" In Chapter 3 a ppropriate conjectures for equitable ? -coloring of disconnected graphs are studied. In Chapter 4 the equitable ?-coloring conjecture for planar graphs are considered . It is proved that each planar graph in various justify; MARGIN: 0cm 0cm 0pt" In Chapter 5 the equitable ?-coloring conjecture for outerplanar graphs are studied. It is proved that every outerplanar graph with maximum degree at most ? admits an equitable k-coloring for every .
اگر در گراف G یک - k رنگ‌آمیزی وجود داشته باشد به‌طوری‌که اختلاف اندازه‌ی کلاس‌های رنگی، حداکثر یک باشد، آنگاه گراف G را -k رنگ‌پذیر منصفانه گویند. کوچکترین عدد صحیح k که به ازای آن گرافG ، -k رنگ‌پذیر منصفانه است را عدد رنگی منصفانه گویند و با نماد نشان می‌دهند. رنگ‌آمیزی منصفانه اولین بار در سال 1973 توسط میر معرفی شده است. میر حدس زد که برای هر گراف همبند G، به جز گراف کامل و دور فرد، . این حدس به حدس رنگ‌آمیزی منصفانه ( ECC ) معروف شد و مورد توجه محققان قرار گرفت. چن و همکارانش در سال 1994 حدس زدند که اگر Gیک گراف همبند غیر از گراف کامل و دور فرد و گراف دوبخشی کامل باشد، آنگاهG ،k - رنگ‌پذیر منصفانه است. این حدس به ( E?CC ) معروف شد. در این پایان‌نامه ضمن مروری بر اهمیت حدس ? - رنگ‌آمیزی منصفانه برای کلاس‌های خاصی از گراف‌ها به طور ویژه به بررسی دقیق ( E? CC ) برای گراف‌های مسطح و ‌گراف‌های مسطح بیرونی می‌پردازیم.

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