k-Colorable Graph

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 {beta_n}_(n=0)={1,1,2,7,41,376,5177,...}" src="https://mathworld.wolfram.com/images/equations/k-ColorableGraph/Inline27.svg" style="height:24px; width:312px" /> (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, ...

---

REFERENCES

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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength