توصيفگر ها :
رنگ آميزي ليستي , رنگ آميزي ليستي يالي , عدد انتخاب , گراف هاي بي نقص بدون پنجه , گراف هاي مقدماتي , خوشه هاي برشي , تري گراف , ستبرسازي
چكيده فارسي :
براي عدد طبيعي 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 منجر به اثبات حدس براي گراف هاي بي نقص بدون پنجه
ساختاري چادنوفسكي و همكاران را براي گراف هاي بي نقصبدون پنجه بررسي كرده ايم و تلاش هايي را براي اثبات حدس
رنگ آميزي ليستي با كمك اين قضيه ساختاري انجام داده ايم.
چكيده انگليسي :
Given a graphG = (V;E) and a natural number k, a k-vertex coloring ofGis a mapping c : V ! f1; 2; : : : ; kg
and the coloring is called valid if every adjacent vertices receive different colors. A graph G is called k-colorable
whenever G admits a valid k-coloring. Also, the minimum number of colors k such that G is k-colorable is called
the chromatic number of G and is denoted by (G). Another type of coloring, first proposed by great scientists such
as Erdős, Rubin, and Taylor in 1978 and Vizing in 1992, is the list coloring. Assumes that for each vertex v 2 V
a list of colors named L(v) is given and we want to find a vertex-coloring named c such that for each vertex v,
c(v) 2 L(v), i.e. the color of each vertex is chosen from its list. Such a coloring is called an L-coloring. The
graph G is called k-choosable if for every list L with the condition jL(v)j = k, for all v 2 V , the graph admits an
L-coloring. The choice number or color-list number of the graph G is the smallest natural number k such that G is
k-choosable and is denoted by ch(G). It is clear that when G is k-choosable, it is also k-colorable since it admits
an L-coloring for the lists L(v) = f1; 2; : : : ; kg, for each v 2 V . So, we can conclude that (G) ch(G).
Now, the natural question that is raised in this direction is whether the opposite side of the inequality is also true or
not? It is easy to find examples where the difference between ch(G) and (G) is very high. Therefore, the answer
to the above question is generally negative. Similarly, we can define the edge version of coloring and list coloring
and the edge chromatic number and edge choice number which are denoted by ′(G) and ch
′
(G), respectively.
Here again, the question is raised whether in any graph like G, ch
′
(G) = ′(G)? This conjecture attributed to
Vizing is known as the list coloring conjecture and still remains unanswered in general. Dinitz’s conjecture which is
essentially the special case of list coloring conjecture for bipartite graphs and its proof by Galvin had a significant
effect in attracting mathematical scientists’attention to the list coloring conjecture. Now, using the concept of line
graphs, the conjecture can be transformed to a vertex coloring problem in the form of whether for every line graph
G, we have (G) = ch(G)? Considering the fact that line graphs is a subclass of claw-free graphs, the conjecture
has also been proposed for claw-free graphs and remained unanswered in both cases.
The thesis investigates a special case of this conjecture for claw-free perfect graphs. A graphGis said to be perfect if
for any induced subgraphH of G, (H) = !(H) where !(H) is the size of the largest clique inH. In this thesis,
main known results related to the conjecture is surveyed. In particular, the proof of the conjecture is reviewed and
elaborated for the complement of triangle-free graphs, cobipartite graphs and peculiar graphs. Then the known results
on claw-free perfect graphs that lead to the proof of the conjecture for claw-free perfect graphs G with !(G) 4
has been collected. Finally, we have investigated the structural theorem of claw-free perfect graphs by Chudnovsky
and Plumettazet and we have made efforts to prove the list coloring conjecture for this class of graph with the aid of
this structural theorem.
