فرض کنیم x(G) عدد رنگی گراف G باشد. دو عبارت زیر را درنظر میگیریم: a) اگر G گراف مسطح با حداقل ۳ رأس باشد، که K_3 زیر گراف G نیست، آنگاه x(G) ≤ ۴ . b) اگر G گراف مسطح با حداقل ۳ رأس باشد که K_4 زیرگراف G نیست، آنگاه x(G) ≤ ۳ . از این دو عبارت کدام درست است؟

سوال ۱۲۷ کنکور ارشد علوم کامپیوتر ۱۴۰۵

اهمیت

۰/۵

فرض کنیم $x(G)$ عدد رنگی گراف $G$ باشد. دو عبارت زیر را درنظر می‌گیریم:

a) اگر $G$ گراف مسطح با حداقل ۳ رأس باشد، که $K_3$ زیر گراف $G$ نیست، آنگاه $x(G) \le ۴$ .

b) اگر $G$ گراف مسطح با حداقل ۳ رأس باشد که $K_4$ زیرگراف $G$ نیست، آنگاه $x(G) \le ۳$ .

از این دو عبارت کدام درست است؟

#chromatic-number#planar-graph#four-color-theorem#graph-coloring#odd-wheel#grotzsch-theorem