المرجع الألكتروني للمعلوماتية
القرآن الكريم وعلومه
العقائد الإسلامية
الفقه وأصوله 
الرجال والحديث 
سيرة الرسول وآله 
علوم اللغة العربية 
الأدب العربي 
الأسرة والمجتمع 
الأخلاق والأدعية 
التاريخ 
الادارة والاقتصاد 
علم الفيزياء 
علم الكيمياء 
علم الأحياء 
الرياضيات 
الهندسة المدنية 
الزراعة 
الجغرافية 
القانون 
اللغة الأنكليزية 
الأخبار 
الإعلام 
مكتبة الصور 
أقلام بمختلف الألوان 
إضاءات
مفتاح
أجوبة الإستفتاءات الشرعية
وثائقيات
تاريخ الرياضيات
الرياضيات في الحضارات المختلفة
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات | k-Colorable Graph |
 1325
 06:37 مساءً
date: 29-3-2022 |
Author : Finch, S. R. 
Book or Source : "Bipartite, k-Colorable and k-Colored Graphs." June 5, 2003. 
Page and Part : ...|
Read More
Date: 18-3-2022
1218
Date: 4-3-2022
1294
Date: 10-4-2022
1974
|
A graph 
having chromatic number 
is called a 
-colorable graph (Harary 1994, p. 127). In contrast, a graph having 
is said to be a k-chromatic graph. Note that 
-colorable graphs are related but distinct from 
-colored graphs.
The 1, 2, 3, and 7, and 13 distinct simple 2-colorable graphs on 
, ..., 5 nodes are illustrated above.
The 1, 2, 4, and 10, and 29 distinct simple 3-colorable graphs on 
, ..., 5 nodes are illustrated above.
The 1, 2, 4, and 11, and 33 distinct simple 4-colorable graphs on 
, ..., 5 nodes are illustrated above.
The following table gives the numbers of 
-colorable simple graphs on 1, 2, ... nodes for small 
.
 |
OEIS | simple graphs on  , 2, ... nodes having  |
| 2 | A033995 | 1, 2, 3, 7, 13, 35, 88, 303, 1119, ... |
| 3 | A076315 | 1, 2, 4, 10, 29, 119, 667, 6024, 88500, ... |
| 4 | A076316 | 1, 2, 4, 11, 33, 150, 985, 11390, 243791, ... |
| 5 | A076317 | 1, 2, 4, 11, 34, 155, 1037, 12257, 272513, ... |
| 6 | A076318 | 1, 2, 4, 11, 34, 156, 1043, 12338, 274541, ... |
| 7 | A076319 | 1, 2, 4, 11, 34, 156, 1044, 12345, 274659, ... |
| 8 | A076320 | 1, 2, 4, 11, 34, 156, 1044, 12346, 274667, ... |
| 9 | A076321 | 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ... |
The 1, 1, 1, 3, and 5 distinct simple connected 2-colorable graphs on 
, ..., 5 nodes are illustrated above.
The 1, 1, 2, and 5, and 17 distinct simple connected 3-colorable graphs on 
, ..., 5 nodes are illustrated above.
The 1, 1, 2, and 6, and 20 distinct simple connected 4-colorable graphs on 
, ..., 5 nodes are illustrated above.
The following table gives the numbers of 
-colorable simple connected graphs on 1, 2, ... nodes for small 
.
 |
OEIS | simple connected graphs on  , 2, ... nodes having  |
| 2 | A005142 | 1, 1, 1, 3, 5, 17, 44, 182, 730, ... |
| 3 | A076322 | 1, 1, 2, 5, 17, 81, 519, 5218, 81677, ... |
| 4 | A076323 | 1, 1, 2, 6, 20, 107, 801, 10227, 231228, ... |
| 5 | A076324 | 1, 1, 2, 6, 21, 111, 847, 11036, 259022, ... |
| 6 | A076325 | 1, 1, 2, 6, 21, 112, 852, 11110, 260962, ... |
| 7 | A076326 | 1, 1, 2, 6, 21, 112, 853, 11116, 261072, ... |
| 8 | A076327 | 1, 1, 2, 6, 21, 112, 853, 11117, 261079, ... |
| 9 | A076328 | 1, 1, 2, 6, 21, 112, 853, 11117, 261080, ... |
The 2 and 7 distinct simple labeled 2-colorable graphs on 
and 3 nodes are illustrated above.
The 2 and 8 distinct simple labeled 3-colorable graphs on 
and 3 nodes are illustrated above.
The following table gives the numbers of labeled 
-colorable graphs on 1, 2, ... nodes for small 
. The sequence 
(OEIS A047864) of 2-colorable labeled graphs on 
nodes has a rather remarkable generating function, as discussed by Wilf (1994, p. 89). Define
 |
giving the sequence 1, 2, 6, 26, 162, ... (OEIS A047863). Then 
is given by
 |
The corresponding problem of enumerating 
-colorable graphs for 
appears to be very hard.
 |
OEIS | labeled graphs on  , 2, ... nodes having  |
| 1 | 1, 1, 1, 1, 1, 1, ... | |
| 2 | A047864 | 1, 2, 7, 41, 376, 5177, ... |
| 3 | A084279 | 1, 2, 8, 63, 958, 27554, ... |
| 4 | A084280 | 1, 2, 8, 64, 1023, 32596, ... |
| 5 | A084281 | 1, 2, 8, 64, 1024, 32767, ... |
| 6 | A084282 | 1, 2, 8, 64, 1024, 32768, ... |
The 1, 3, and 19 distinct simple connected labeled 2-colorable graphs on 
, 3, and 4 nodes are illustrated above.
The 1, 4, and 37 distinct simple connected labeled 3-colorable graphs on 
, 3, and 4 nodes are illustrated above.
The following table gives the numbers of connected labeled 
-colorable graphs on 1, 2, ... nodes for small 
.
 |
OEIS | connected labeled graphs on  , 2, ... nodes having  |
| 1 | 1, 0, 0, 0, 0, ... | |
| 2 | A001832 | 1, 1, 3, 19, 195, 3031, 67263, ... |
| 3 | A084283 | 1, 1, 4, 37, 667, 21886, ... |
| 4 | A084284 | 1, 1, 4, 38, 727, 26538, ... |
| 5 | A084285 | 1, 1, 4, 38, 728, 26703, ... |
| 6 | A084286 | 1, 1, 4, 38, 728, 26704, ... |
Finch, S. R. "Bipartite, 
-Colorable and 
-Colored Graphs." June 5, 2003.
http://algo.inria.fr/bsolve/.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
Sloane, N. J. A. Sequences A001832/M3063, A005142/M2501, A033995, A047864, A076315, A076316, A076317, A076318, A076319, A076320, A076321, A076322, A076323, A076324, A076325, A076326, A076327, A076328, A084279, A084280, A084281, A084282, A084283, A084284, A084285, and A084286 in "The On-Line Encyclopedia of Integer Sequences.
"Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, p. 89, 1993.
|
|
|
|
"تهديد صامت" قد يزيد من خطر إصابة غير المدخنين بسرطان الرئة
|
|
|
|
|
|
|
نجاح أول تجربة تجول لبعثة خاصة بالفضاء في التاريخ
|
|
|
|
|
|
|
شُعبة التّوجيه الدّيني تعقُد مجلس عزاء بذكرى استشهاد الإمام العسكري (عليه السّلام)
|
|
|
