المرجع الألكتروني للمعلوماتية
القرآن الكريم وعلومه
العقائد الإسلامية
الفقه وأصوله 
الرجال والحديث 
سيرة الرسول وآله 
علوم اللغة العربية 
الأدب العربي 
الأسرة والمجتمع 
الأخلاق والأدعية 
التاريخ 
الادارة والاقتصاد 
علم الفيزياء 
علم الكيمياء 
علم الأحياء 
الرياضيات 
الهندسة المدنية 
الزراعة 
الجغرافية 
القانون 
اللغة الأنكليزية 
الأخبار 
الإعلام 
مكتبة الصور 
أقلام بمختلف الألوان 
إضاءات
مفتاح
أجوبة الإستفتاءات الشرعية
وثائقيات
تاريخ الرياضيات
الرياضيات في الحضارات المختلفة
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات | k-Colorable Graph |
 1414
 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: 10-3-2022
1491
Date: 21-4-2022
1637
Date: 22-5-2022
3907
|
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.
|
|
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|
