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

در اين مقاله، عدد رنگي χاحاطه گر، يعني d_χ (G) در يك گراف G مورد بررسي قرار مي گيرد. اين عدد برابر است با ماكزيمم تعداد رده هاي رنگي كه احاطه گر (يا تسلطي) بوده و G توسط χ(G) رنگ، رنگ آميزي مي شود. همچنين، نشان خواهيم داد كه d_χ (G∨H)=d_χ (G)+d_χ (H) است بطوريكه G∨H به معناي الحاق G و H است. نتيجه فوق به ما كمك مي كند كه رده هاي گراف هايي كه d_χ (G) gt;1 و d_χ (G)=χ(G) است را مشخص نماييم. همچنين در اين مقاله، برخي نتايج در ارتباط با عدد رنگي χاحاطه گر يك گراف ارائه مي شود كه مرتبط با سوالات مطرح شده در برخي مقالات اخير حول مشخص سازي گراف هاي همبند G براساس مقدار d_χ (G) مي باشد. در بخش پاياني مقاله، براساس قضاياي حاصل اين پرسش را مطرح مي كنيم كه آيا گراف هاي بدون مثلث G با شرط d_χ (G )=χ(G)=k موجود است؟آيا G داراي يك زيرگراف kرنگ پذير يكتا است يا خير؟ بعلاوه، آيا يافتن چنين گراف هايي از كمر به اندازه كافي بزرگ ميسر مي باشد؟