9349

8631

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

علوم رياضي - رياضي كاربردي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي

1393

[هشت]،84ص.:جدول

ص.ع.به فارسي و انگليسي

بهناز عمومي

رامين جوادي

17/9/93

غلامرضا اميدي، محمدرضا عبودي

رياضي

ID8631

Equitable Coloring of Graphs Fatemeh Kiani fatemeh kiani@math iut ac ir September 09 2014 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Behnaz Omoomi bomoomi@cc iut ac ir Advisor Dr Ramin Javadi rjavadi@cc iut ac ir 2010 MSC 05C15 Keywords Vertex coloring Equitable coloring Planar graphs Outer planar graphs AbstractIf the vertices of a graph G are colored with k colors such that no adjacent vertices receivethe same color and the sizes of any two color classes di er by at most one then G is said tobe equitably k colorable The equitable chromatic number G is the smallest integer ksuch that G is equitably k colorable The notion of an equitable coloring was rst introduced by W Meyer His motivation camefrom Tucker s paper in which vertices represent garbage collection routes and two such ver tices are adjacent when the corresponding routes should not be run on the same day Meyerthought that it would be desirable to have an approximately equal number of routes run oneach of the 6 days in a week T The main result obtained by Meyer was that a tree T can be equitably colored with 1 2colors However there were gaps in his proof According to Guy s report Eggleton couldextend Meyer s result to show that a tree T can be equitably colored with k colors provided T k 1 2The most interesting contribution made in Meyer s paper is to propose the following conjec ture

بهناز عمومي

رامين جوادي

غلامرضا اميدي، محمدرضا عبودي