بررسی بیشینه تعداد رده های احاطه گر در رنگ آمیزی یک گراف

در این مقاله، عدد رنگی χاحاطه گر، یعنی 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رنگ پذیر یکتا است یا خیر؟ بعلاوه، آیا یافتن چنین گراف هایی از کمر به اندازه کافی بزرگ میسر می باشد؟