12828

11738

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

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

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

1396

[نه]، [120]ص.: مصور، جدول، نمودار

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

واژه نامه انگليسي به فارسي

1396/07/03

كتابنامه

علوم رياضي

رياضي

ID11738

Injective Coloring of Graphs Mahsa Mozafari Nia m mozafari@math iut ac ir August 27 2017 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Behnaz Omoomi bomoomi@cc iut ac ir 2010 MSC 05C15 Keywords Injective coloring Injective chromatic number Planar graph Outerplanargraph AbstractA proper k coloring of a graph G is a mapping from V G to the set of colors 1 2 k such that any two adjacent vertices have di erent colors The chromatic number G is a minimum integer k that G has a proper k coloring A coloring c of G is called aninjective coloring if for every two vertices u and v which have common neighbor c u c v That means the restriction of c to the neighborhood of any vertex is an injective function The injective chromatic number denoted by i G is the least integer k such that G has aninjective k coloring Note that an injective coloring is not necessarily a proper coloring In fact i G G 2 where V G 2 V G and uv E G 2 if and only if u and v have acommon neighbor in G The square of graph G denoted by G2 is a graph with vertex setV G where two vertices are adjacent in G2 if and only if they are at distance at most twoin G Since G 2 is a subgraph of G2 obviously i G G2 The concept of injectivecoloring is introduced by Hahn et al in 2002 Discrete Mathematics 256 1 2 179 192 It is clear that for every graph G i G In general Hahn et al proved that i G 2 1

بهناز عمومي

زينب مالكي، علي بهتويي