بررسی بیشینه تعداد رده های احاطه گر در رنگ آمیزی یک گراف
الموضوعات :
مرتضی فغانی
1
(دانشکده ریاضی، دانشگاه پیام نور، کدپستی 3697-19395 تهران، ایران)
الکلمات المفتاحية: Dominating Coloring Classes, Dominating Sets, Dominating Color Number, Chromatic number, Graph Coloring,
ملخص المقالة :
در این مقاله، عدد رنگی χ-احاطه گر، یعنی d_χ (G) در یک گراف G مورد بررسی قرار می گیرد. این عدد برابر است با ماکزیمم تعداد رده های رنگی که احاطه گر (یا تسلطی) بوده و G توسط χ(G) رنگ، رنگ آمیزی می شود. همچنین، نشان خواهیم داد که d_χ (G∨H)=d_χ (G)+d_χ (H) است بطوریکه G∨H به معنای الحاق G و H است. نتیجه فوق به ما کمک می کند که رده های گراف هایی که d_χ (G)>1 و d_χ (G)=χ(G) است را مشخص نماییم. همچنین در این مقاله، برخی نتایج در ارتباط با عدد رنگی χ-احاطه گر یک گراف ارائه می شود که مرتبط با سوالات مطرح شده در برخی مقالات اخیر حول مشخص سازی گراف های همبند G براساس مقدار d_χ (G) می باشد. در بخش پایانی مقاله، براساس قضایای حاصل این پرسش را مطرح می کنیم که آیا گراف های بدون مثلث G با شرط d_χ (G )=χ(G)=k موجود است؟آیا G دارای یک زیرگراف k-رنگ پذیر یکتا است یا خیر؟ بعلاوه، آیا یافتن چنین گراف هایی از کمر به اندازه کافی بزرگ میسر می باشد؟
[1] Arumugam, S., Haynes, T.W., Henning, M.A. and Nigussie, Y., Maximal Independent Sets in Minimum Colorings. Discrete Mathematics, 311 (2011) 1158-1163.
[2] Arumugam, A., Hamid, I.S. and Muthukamatchi, A., Independent Domination and Graph Clorings. Ramanujan Mathematical Society Lecture Notes Series, 7 (2008) 195-203.
[3] Arumugam, S. and Chandrasekar, K.R., Minimal Dominating Sets in Maximum Domatic Partitions. Australasian Journal of Combinatorics, 52 (2012) 281-292.
[4] Li, S., Zhang, H. and Zhang, X., Maximal Independent Sets in Bipartite Graphs with at Least One Cycle. Discrete Mathematics and Theoretical Computer Science, 15 (2013) 243-258.
