Uniquely k-Colorable Graph

A uniquely -colorable graph  is a -colorable graph such that every -coloring gives the same partition of  (Chao 2001).

Chao (2001) proved that there exist uniquely -colorable graphs with  and  vertices for every integer , and that there exit two uniquely -colorable graphs  and  vertices that are chromatically equivalent.

The graph illustrated above is a 12-vertex 22-edge triangle-free graph that is three-colorable in exactly one way modulo permutations of colors (Harary et al. 1970). It is implemented in the Wolfram Language as GraphData["UniquelyThreeColorableGraph"], replacing the incorrect graph from Harary (1994, cover and p. 139).

Unfortunately, Harary et al. (1969; left bottom figure) and Harary (1994, p. 139; top and bottom right figures) give not just one but two incorrect versions of this graph. Neither of these is uniquely three-colorable, as can be seen by noting that in the left graph, the lower right-hand green vertex can be replaced with blue, whereas in the right graph, the lower left-hand red vertex can be replaced with blue.

Osterweil (1974) and Chao and Chen (1993) gave families of uniquely 3-colorable graphs without and with triangles, respectively.

---

REFERENCES

Chao, C.-Y. "Uniquely -Colorable and Chromatically Equivalent Graphs." Bull. Malays. Math. Sci. Soc. 24, 3-103, 2001.

Chao, C.-Y. and Chen, Z. "On Uniquely 3-Colorable Graphs." Disc. Math. 112, 21-27, 1993.

Chia, G. L. "On Graphs Uniquely Colorable under the Action of Their Automorphism Groups." Disc. Math. 162, 281-284, 1996.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Harary, F.; Hedetniemi, S.; and Robinson, R. "Erratum to 'Uniquely Colorable Graphs'." J. Combin. Th. 9, 221, 1970.

Harary, F.; Hedetniemi, S.; and Robinson, R. "Uniquely Colorable Graphs." J. Combin. Th. 6, 264-270, 1969.

Osterweil, L. J. "Some Classes of Uniquely 3-Colorable Graphs." Disc. Math. 8, 59-69, 1974.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.

اخر الاخبار

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

مكتب المتولي الشرعي للشؤون النسوية يناقش استعداداته لإقامة مهرجان روح النبوة الثامن وحفل تخرج الطالبات العاشر

الهيأة العليا لإحياء التراث تشارك بمؤتمر دولي عن السيد الميلاني (قدس سره) في إيران

وفد متحف الكفيل يطّلع على النفائس والوثائق التاريخية في متاحف العتبة الرضوية المقدسة

قسم الشؤون الطبية يواصل تنظيم ورش تدريبية لرفع كفاءة المنتسبين في الإسعافات الأولية

المزيد

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

خصوصا مع تقدم السن.. 6 سلوكيات يومية قد تدمّر صحتك

فاكهة خضراء.. علاج طبيعي فعّال للإمساك واضطرابات الهضم

روسيا تبدأ أولى التجارب السريرية للقاح واعد ضد السرطان

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

المزيد

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

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

روسيا تخطط لإقامة محطة نووية في القمر خلال العقد المقبل

كيف قاد إيلون ماسك حملة "غروك" لاختراق عرش الذكاء الاصطناعي

ألتمان: الذكاء الاصطناعي سيتجاوز البشر في 2026 !

المزيد

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

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