با توجه به اين که الگوريتم بهينه سازي فاخته يک الگوريتم جامع و بسيار سريع مي باشد لذا بايد قادر باشد تا انواع مسائل بهينه سازي را حل نمايد. يکي از انواع مسائل گسسته اي که با استفاده از اين الگوريتم حل شده است، مسئله رنگ آميزي گراف است. در نظريه گراف، رنگ آميزي گراف يکي از حالت هاي خاص مساله هاي برچسب گذاري گراف است. رويکرد کلي آن استفاده از نظير کردن رنگ هايي به يال ها يا راس ها است که اين رنگ آميزي محدوديت خاصي را رعايت نمايد. در ساده ترين حالت، رنگ آميزي مورد نظر است که در آن هيچ دو راس مجاوري هم رنگ نباشند (رنگ آميزي راس ها). علاوه بر آن رنگ آميزي يال ها نيز به همين صورت تعريف مي شود. رنگ آميزي گراف کاربردهاي زيادي در زمينه هاي عملي و تئوري گوناگون دارد. با وجود اين که اين مساله از نظر علمي هنوز در حال رشد و بررسي بيشتر مي باشد، با ظهور جدول سودوکو در بين عموم مردم شناخته و مشهور شده است.
براي حل مسائل بهينه سازي گسسته با الگوريتم بهينه سازي فاخته لازم است تا موقعيت هاي سکونت فاخته ها از حالت پيوسته به گسسته تبديل شود. ساده ترين روش انجام چنين کاري round گيري از habitat (محل سکونت) هاي فاخته ها است. سپس با تعريف مناسب تابع هزينه مي توان از الگوريتم بهينه سازي فاخته انتظار داست که کمترين تعداد رنگ ها را چنان به راس هاي هر گراف دلخواه اختصاص دهد که هيچ گره مجاوري که با يالي بهم وصل هستند داراي رنگ يکساني نباشند. براي اين کار کافيست دو مورد را در تابع هزينه لحاظ کنيم:
- در هر تکرار الگوريتم بهينه سازي فاخته به ازاي هر عضو از جمعيت که جواب کانديدي براي حل مساله است، در صورتي که مقدار عددي رنگ اختصاص داده شده به راس هاي مجاور يکسان باشد مقدار هزينه اين جواب بايد افزايش داشته باشد. براي اين کار مي توان شمارنده اي در نظر گرفت که به ازاي هر بار نقض اين شرط يک واحد به آن افزوده شود.
- با قيد فوق فقط راس هاي مجاور که با يالي بهم وصل شده اند داراي رنگ يکساني نخواهند بود ولي شرط استفاده از مينيمم رنگ برآورده نخواهد شد. براي برآورده شدن اين شرط بايد جمله ديگري به تابع هزينه اضافه کينم. اين جمله بدين صورت است که اگر دو راس در گراف داراي رنگ هاي يکساني نباشند و بين آن ها يالي موجود نباشد آن گاه مقدار تابع هزينه باز هم افزايش خواهد داشت. براي اين کار هم مي توان از شمارنده ي ديگري استفاده کرد.
در نهايت مي توان مقدار دو پارامتر جريمه فوق را با ضرايبي جمع کرده و بعنوان تابع هزينه با الگوريتم بهينه سازي فاخته جهت کمينه سازي ارائه کرد.