সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনার b-ক্রোমেটিক সংখ্যা নির্ধারণ

মৌলিক তথ্য

• পেপার আইডি: 2302.13667
• শিরোনাম: সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনার b-ক্রোমেটিক সংখ্যা নির্ধারণ
• লেখক: Raúl M. Falcón (Universidad de Sevilla, Spain), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
• শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা)
• প্রকাশনার সময়: ২০২৩ সালের ২৭ ফেব্রুয়ারি
• পেপার লিঙ্ক: https://arxiv.org/abs/2302.13667

সারসংক্ষেপ

ধরা যাক $G$ এবং $H$ দুটি গ্রাফ, যার প্রতিটি পথ, চক্র বা তারকা গ্রাফ। এই পেপারটি প্রতিটি সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনা গ্রাফ $G\boxdot H$ বা $G\boxdot K_n$ এর b-ক্রোমেটিক সংখ্যা নির্ধারণ করে, যেখানে $K_n$ হল $n$ ক্রমের সম্পূর্ণ গ্রাফ। $m$-ডিগ্রি যা $n+2$ এর চেয়ে বেশি নয় এমন গ্রাফ $K_n\boxdot G$ এর জন্যও সংশ্লিষ্ট ফলাফল প্রতিষ্ঠিত হয়েছে। সমস্ত প্রমাণ বর্ণনামূলক উদাহরণ সহ সরবরাহ করা হয়েছে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

1. b-ক্রোমেটিক সংখ্যার ধারণা: Irving এবং Manlove ১৯৯৯ সালে গ্রাফের b-রঙ্গ ধারণা প্রবর্তন করেছিলেন, যা একটি বিশেষ সাধারণ $k$-রঙ্গ, যেখানে প্রতিটি রঙের একটি b-শীর্ষ থাকে (যে শীর্ষটি অন্য সমস্ত রঙের শীর্ষের সাথে সংলগ্ন)।
2. গণনামূলক জটিলতা: গ্রাফের b-ক্রোমেটিক সংখ্যা নির্ধারণ সাধারণ ক্ষেত্রে NP-কঠিন সমস্যা, কিন্তু গাছের জন্য বহুপদী সময়ে সমাধানযোগ্য।
3. গ্রাফ পণ্য গবেষণা: বিভিন্ন গ্রাফ পণ্যের b-ক্রোমেটিক সংখ্যা সম্পর্কে ব্যাপক গবেষণা রয়েছে, যেমন কার্টেসিয়ান পণ্য, সরাসরি পণ্য, শক্তিশালী পণ্য, অভিধান ক্রম পণ্য ইত্যাদি।

গবেষণার প্রেরণা

1. তাত্ত্বিক সম্পূর্ণতা: সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনা গ্রাফ (SVN করোনা) একটি গুরুত্বপূর্ণ গ্রাফ নির্মাণ পদ্ধতি, কিন্তু এর b-ক্রোমেটিক সংখ্যা গবেষণা তুলনামূলকভাবে অপর্যাপ্ত।
2. পদ্ধতির সিস্টেমেটাইজেশন: মৌলিক গ্রাফ শ্রেণী (পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফ) এর SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা সিস্টেমেটিকভাবে অধ্যয়ন করার প্রয়োজন।
3. প্রয়োগের মূল্য: b-ক্রোমেটিক সংখ্যা নেটওয়ার্ক রঙ্গ, ফ্রিকোয়েন্সি বরাদ্দ ইত্যাদি বাস্তব সমস্যায় গুরুত্বপূর্ণ প্রয়োগ রয়েছে।

মূল অবদান

1. মৌলিক গ্রাফ শ্রেণীর SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা সম্পূর্ণভাবে নির্ধারণ করা: পথ $P_n$, চক্র $C_n$, তারকা গ্রাফ $S_n$ এবং পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফের SVN করোনার জন্য নির্ভুল b-ক্রোমেটিক সংখ্যা সূত্র প্রদান করা।
2. সম্পূর্ণ গ্রাফ SVN করোনা গ্রাফের আংশিক ফলাফল প্রতিষ্ঠা করা: $m$-ডিগ্রি $n+2$ এর চেয়ে বেশি না হওয়া $K_n\boxdot G$ এর জন্য, এর b-ক্রোমেটিক সংখ্যা নির্ধারণ করা।
3. নির্মাণমূলক প্রমাণ পদ্ধতি প্রদান করা: সমস্ত ফলাফল নির্দিষ্ট সর্বোত্তম b-রঙ্গ রঙ নির্মাণের মাধ্যমে প্রমাণিত হয়েছে এবং বিস্তারিত গ্রাফ উদাহরণ সহ সরবরাহ করা হয়েছে।
4. সিস্টেমেটিক বিশ্লেষণ কাঠামো বিকাশ করা: SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা বিশ্লেষণের জন্য একটি সাধারণ পদ্ধতি এবং প্রযুক্তিগত সরঞ্জাম প্রতিষ্ঠা করা।

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

ইনপুট: দুটি গ্রাফ $G$ এবং $H$, যেখানে $G,H \in \{P_n, C_n, S_n, K_n\}$আউটপুট: SVN করোনা গ্রাফ $G\boxdot H$ এর b-ক্রোমেটিক সংখ্যা $\varphi(G\boxdot H)$সীমাবদ্ধতা: $K_n\boxdot G$ এর ক্ষেত্রে, $m(K_n\boxdot G) \leq n+2$ প্রয়োজন

SVN করোনা গ্রাফ নির্মাণ

গ্রাফ $G$ এবং $H$ দেওয়া, SVN করোনা গ্রাফ $G\boxdot H$ এর নির্মাণ প্রক্রিয়া:

1. গ্রাফ $G$ এর সাবডিভিশন গ্রাফ $S(G)$ থেকে শুরু করুন (প্রতিটি প্রান্তে একটি নতুন শীর্ষ সন্নিবেশ করান)
2. $|V(G)|$ টি $H$ এর শীর্ষ-বিচ্ছিন্ন অনুলিপি যোগ করুন
3. $S(G)$ এর প্রতিটি মূল শীর্ষ $u_i$ এর নেইবারহুডের সমস্ত শীর্ষকে $(i+1)$ তম $H$ অনুলিপির সমস্ত শীর্ষের সাথে সংযুক্ত করুন

মূল প্রযুক্তিগত সরঞ্জাম

1. m-ডিগ্রি ধারণা

$n$ ক্রমের গ্রাফ $G$ এর জন্য, এর m-ডিগ্রি সংজ্ঞায়িত করা হয়: $m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}|$ যেখানে শীর্ষগুলি ডিগ্রির অ-বর্ধমান ক্রমে সাজানো হয়।

2. মৌলিক সীমাবদ্ধতা

• নিম্ন সীমা: $\chi(G) \leq \varphi(G)$ (ক্রোমেটিক সংখ্যা b-ক্রোমেটিক সংখ্যা অতিক্রম করে না)
• উচ্চ সীমা: $\varphi(G) \leq \Delta(G) + 1$ (b-ক্রোমেটিক সংখ্যা সর্বোচ্চ ডিগ্রি যোগ এক অতিক্রম করে না)
• m-ডিগ্রি সীমাবদ্ধতা: $\varphi(G) \leq m(G)$

3. SVN করোনা গ্রাফের ডিগ্রি সূত্র

$G\boxdot H$ এ শীর্ষ $v$ এর জন্য: $d_{G\boxdot H}(v) = \begin{cases} d_G(v), & \text{যদি } v \in V(G) \\ 2|V(H)| + 2, & \text{যদি } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{যদি } v = v_{i,j} \end{cases}$

বিশ্লেষণ কৌশল

পেপারটি বিভিন্ন গ্রাফ শ্রেণী সমন্বয়ের জন্য শ্রেণীবিভাগ আলোচনা পদ্ধতি ব্যবহার করে:

1. পথের SVN করোনা গ্রাফ (তৃতীয় অংশ)
2. চক্রের SVN করোনা গ্রাফ (চতুর্থ অংশ)
3. তারকা গ্রাফের SVN করোনা গ্রাফ (পঞ্চম অংশ)
4. সম্পূর্ণ গ্রাফের SVN করোনা গ্রাফ (ষষ্ঠ অংশ)

প্রতিটি ক্ষেত্রে নির্দিষ্ট b-রঙ্গ রঙ নির্মাণের মাধ্যমে উচ্চ সীমার কঠোরতা প্রমাণিত হয়।

প্রধান ফলাফল

পথের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা

উপপাদ্য 6 ($P_n \boxdot P_t$): $\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{যদি } n=3 \text{ এবং } t \in \{3,4\} \\ 5, & \text{যদি } (n=3 \text{ এবং } t \geq 5) \text{ বা } n \in \{4,5\} \\ n-1, & \text{যদি } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{অন্যথায়} \end{cases}$

উপপাদ্য 7-9: অনুরূপভাবে $P_n \boxdot C_t$, $P_n \boxdot S_t$, $P_n \boxdot K_t$ এর নির্ভুল সূত্র প্রদান করা হয়েছে।

চক্রের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা

উপপাদ্য 11 ($C_n \boxdot P_t$): $\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{যদি } n \in \{3,4\} \\ n, & \text{যদি } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{অন্যথায়} \end{cases}$

তারকা গ্রাফের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা

উপপাদ্য 17: তারকা গ্রাফ এবং মৌলিক গ্রাফ শ্রেণীর SVN করোনা গ্রাফের জন্য, সম্পূর্ণ b-ক্রোমেটিক সংখ্যা সূত্র প্রতিষ্ঠিত হয়েছে, যেখানে মূল ফলাফল অন্তর্ভুক্ত: $\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$

সম্পূর্ণ গ্রাফের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা

উপপাদ্য 20-24: m-ডিগ্রি সীমাবদ্ধতার অধীনে, $K_n\boxdot G$ এর b-ক্রোমেটিক সংখ্যা প্রদান করা হয়েছে, উদাহরণস্বরূপ: $\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{নির্দিষ্ট শর্তাবলী} \\ n+2, & \text{অন্যান্য শর্তাবলী} \end{cases}$

প্রযুক্তিগত উদ্ভাবন বিন্দু

1. নির্মাণমূলক প্রমাণ পদ্ধতি

• শুধুমাত্র উচ্চ সীমা প্রমাণ করা নয়, বরং স্পষ্ট নির্মাণের মাধ্যমে সর্বোত্তম b-রঙ্গ রঙ প্রমাণ করে নিম্ন সীমা প্রমাণ করা
• প্রতিটি নির্মাণ বিস্তারিত গ্রাফ উদাহরণ সহ সরবরাহ করা হয়েছে, ফলাফলের যাচাইযোগ্যতা বৃদ্ধি করে

2. b-রংধনু সেট ধারণা

b-শীর্ষ সনাক্তকরণ সহজ করার জন্য b-রংধনু সেটের ধারণা প্রবর্তন করা হয়েছে, গ্রাফে বিভিন্ন প্রতীক দিয়ে চিহ্নিত:

• ক্রস ×: নির্দিষ্ট b-রংধনু সেটের শীর্ষ
• ত্রিভুজ △: অন্যান্য b-শীর্ষ
• বৃত্ত ●: সাধারণ শীর্ষ

3. মডুলার পাটিগণিত কৌশল

রঙ নির্মাণে ব্যাপকভাবে মডুলার পাটিগণিত ব্যবহার করা হয় রঙের পর্যায়ক্রমিকতা এবং সঠিকতা নিশ্চিত করতে, উদাহরণস্বরূপ: $c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$

4. শ্রেণীবিভাগ আলোচনার সিস্টেমেটাইজেশন

প্যারামিটার পরিসীমা অনুযায়ী সূক্ষ্ম শ্রেণীবিভাগ আলোচনা, সমস্ত সম্ভাব্য ক্ষেত্র কভার নিশ্চিত করে।

পরীক্ষামূলক যাচাইকরণ

গ্রাফ যাচাইকরণ

পেপারটি তাত্ত্বিক ফলাফল যাচাই করার জন্য অসংখ্য গ্রাফ উদাহরণ প্রদান করে:

• চিত্র 2: $P_{10} \boxdot P_3$ এর সর্বোত্তম b-রঙ্গ রঙ
• চিত্র 3-4: বিভিন্ন প্যারামিটারে পথের SVN করোনা গ্রাফের রঙ
• চিত্র 11: চক্রের SVN করোনা গ্রাফের রঙ উদাহরণ
• চিত্র 17-18: তারকা গ্রাফের SVN করোনা গ্রাফের রঙ নির্মাণ

নির্মাণ যাচাইকরণ

প্রতিটি উপপাদ্যের প্রমাণে নির্দিষ্ট রঙ নির্মাণ অ্যালগরিদম অন্তর্ভুক্ত রয়েছে, যা সরাসরি যাচাই করা যায়:

1. রঙের সঠিকতা (সংলগ্ন শীর্ষ বিভিন্ন রঙ)
2. b-শীর্ষের অস্তিত্ব (প্রতিটি রঙের একটি b-শীর্ষ রয়েছে)
3. সর্বোত্তমতা (তাত্ত্বিক সীমা অর্জন করে)

সম্পর্কিত কাজ

b-ক্রোমেটিক সংখ্যা গবেষণার ইতিহাস

1. Irving-Manlove (1999): প্রথমবার b-ক্রোমেটিক সংখ্যা ধারণা প্রবর্তন করা
2. বিভিন্ন গ্রাফ পণ্যের গবেষণা: কার্টেসিয়ান পণ্য, সরাসরি পণ্য, শক্তিশালী পণ্য ইত্যাদির b-ক্রোমেটিক সংখ্যা ব্যাপকভাবে অধ্যয়ন করা হয়েছে
3. বিশেষ গ্রাফ শ্রেণী: পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফের b-ক্রোমেটিক সংখ্যা পরিচিত

এই পেপারের অবস্থান

• শূন্যতা পূরণ: SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা গবেষণা তুলনামূলকভাবে অপর্যাপ্ত
• পদ্ধতি উদ্ভাবন: সিস্টেমেটিক নির্মাণ পদ্ধতি প্রদান করা
• ফলাফল সম্পূর্ণতা: মৌলিক গ্রাফ শ্রেণী সমন্বয়ের সম্পূর্ণ ফলাফল প্রদান করা

উপসংহার এবং আলোচনা

প্রধান সিদ্ধান্ত

1. সম্পূর্ণতা: মৌলিক গ্রাফ শ্রেণী (পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফ) এর SVN করোনা গ্রাফের জন্য, সম্পূর্ণ b-ক্রোমেটিক সংখ্যা নির্ধারণ ফলাফল প্রদান করা হয়েছে
2. নির্ভুলতা: সমস্ত ফলাফল নির্ভুল মান, অনুমান বা সীমাবদ্ধতা নয়
3. নির্মাণমূলকতা: নির্দিষ্ট সর্বোত্তম রঙ নির্মাণ পদ্ধতি প্রদান করা হয়েছে

সীমাবদ্ধতা

1. গ্রাফ শ্রেণী সীমাবদ্ধতা: শুধুমাত্র মৌলিক গ্রাফ শ্রেণী বিবেচনা করা হয়েছে, সাধারণ গ্রাফের ফলাফল আরও গবেষণার অপেক্ষায় রয়েছে
2. সম্পূর্ণ গ্রাফ সীমাবদ্ধতা: $K_n\boxdot G$ এর ফলাফলের জন্য m-ডিগ্রি সীমাবদ্ধতা শর্ত প্রয়োজন
3. জটিলতা: কিছু ক্ষেত্রে শ্রেণীবিভাগ আলোচনা অত্যন্ত জটিল

ভবিষ্যত দিকনির্দেশনা

1. গ্রাফ শ্রেণী সম্প্রসারণ: আরও সাধারণ গ্রাফ শ্রেণীর SVN করোনা গ্রাফ b-ক্রোমেটিক সংখ্যা গবেষণা করা
2. অ্যালগরিদম গবেষণা: দক্ষ b-ক্রোমেটিক সংখ্যা গণনা অ্যালগরিদম বিকাশ করা
3. প্রয়োগ অন্বেষণ: ফলাফল বাস্তব নেটওয়ার্ক রঙ সমস্যায় প্রয়োগ করা

গভীর মূল্যায়ন

সুবিধা

1. উল্লেখযোগ্য তাত্ত্বিক অবদান: একটি গুরুত্বপূর্ণ গ্রাফ পণ্য শ্রেণীর b-ক্রোমেটিক সংখ্যা সমস্যা সিস্টেমেটিকভাবে সমাধান করা
2. কঠোর পদ্ধতি: নির্মাণমূলক প্রমাণ পদ্ধতি ফলাফলের নির্ভরযোগ্যতা নিশ্চিত করে
3. স্পষ্ট উপস্থাপনা: অসংখ্য গ্রাফ এবং উদাহরণ জটিল প্রমাণ বোঝা সহজ করে
4. সম্পূর্ণ ফলাফল: মৌলিক গ্রাফ শ্রেণীর সমস্ত গুরুত্বপূর্ণ সমন্বয় কভার করে

অপূর্ণতা

1. সীমিত প্রযুক্তিগত উদ্ভাবন: প্রধানত বিদ্যমান পদ্ধতির সিস্টেমেটিক প্রয়োগ, মৌলিক নতুন প্রযুক্তির অভাব
2. অস্পষ্ট প্রয়োগের মূল্য: বাস্তব প্রয়োগ পরিস্থিতির আলোচনার অভাব
3. গণনামূলক জটিলতা বিশ্লেষণ অনুপস্থিত: নির্মাণ অ্যালগরিদমের সময় জটিলতা আলোচনা করা হয়নি

প্রভাব

1. তাত্ত্বিক মূল্য: গ্রাফের b-ক্রোমেটিক সংখ্যা তত্ত্বে গুরুত্বপূর্ণ সম্পূরক প্রদান করে
2. পদ্ধতি মূল্য: নির্মাণ পদ্ধতি অন্যান্য গ্রাফ পণ্য গবেষণায় সাধারণীকরণ করা যায়
3. সম্পূর্ণতা মূল্য: SVN করোনা গ্রাফ b-ক্রোমেটিক সংখ্যা গবেষণার শূন্যতা পূরণ করে

প্রযোজ্য পরিস্থিতি

1. তাত্ত্বিক গবেষণা: গ্রাফ তত্ত্ব এবং সমন্বয় অপ্টিমাইজেশন ক্ষেত্রের মৌলিক গবেষণা
2. নেটওয়ার্ক ডিজাইন: নেইবারহুড সীমাবদ্ধতা বিবেচনা করে এমন নেটওয়ার্ক রঙ সমস্যা
3. অ্যালগরিদম ডিজাইন: আরও জটিল গ্রাফ রঙ অ্যালগরিদমের মৌলিক মডিউল হিসাবে

সংদর্ভ

পেপারটি ২৫টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, যার মধ্যে প্রধানগুলি অন্তর্ভুক্ত:

• Irving & Manlove (1999): b-ক্রোমেটিক সংখ্যার মূল সংজ্ঞা
• Kouider & Mahéo ইত্যাদি: বিভিন্ন গ্রাফ পণ্যের b-ক্রোমেটিক সংখ্যা গবেষণা
• Liu & Lu (2013): SVN করোনা গ্রাফের বর্ণালী তত্ত্ব গবেষণা
• Brooks (1941): গ্রাফ রঙের ক্লাসিক ফলাফল