The Smallest Number of Colors Needed for a‎ ‎Coloring of the Square of the Cartesian Product of Certain Graphs
Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
Given any graph G‎, ‎its square graph G^2 has the same vertex set as G, ‎with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. ‎‎The Cartesian product of graphs G and H is denoted by G□ H. ‎‎One of the most studied NP-hard problems is the graph coloring problem‎. A method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by researchers for many years‎. ‎In this paper‎, ‎we use the graph product approach to this problem‎. ‎In fact‎, ‎we prove that X((D(m',n')□D(m,n))^2)<= 10 for m,n => 3, ‎where D(m‎, ‎n) is the graph obtained by joining a vertex of the cycle C_m to a vertex of degree one of the paths P_n and X(G) is the chromatic number of the graph $G$.
Language:
English
Published:
Control and Optimization in Applied Mathematics, Volume:8 Issue: 1, Winter-Spring 2023
Pages:
83 to 93
magiran.com/p2586810  
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یک‌ساله به مبلغ 990,000ريال می‌توانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
  • حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران می‌شود.
  • پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانه‌های چاپی و دیجیتال را به کاربر نمی‌دهد.
In order to view content subscription is required

Personal subscription
Subscribe magiran.com for 50 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!