Abstrakt

Chromatische Polynome

Karrie Williams

Wenn es darum geht, die Knoten eines Graphen unter bestimmten Einschränkungen zu färben, gibt es viele faszinierende Schwierigkeiten zu erforschen, die einen schnellen Überblick über die Grundlagen dieses Abschnitts der Graphentheorie bieten. Die Färbung eines Graphen wird erreicht, indem jedem Knoten im Graphen eine Farbe aus einer Reihe von Farben zugewiesen wird. Es handelt sich um eine Übersetzung der Knoten in (oder auf) eine Menge s C, in formaleren Worten (die Menge der Farben). Wir werden die Debatte darüber, ob die Abbildungen in oder auf erfolgen sollten, vorerst beiseite legen. Eine geeignete Färbung eines Graphen ist eine, die die Einschränkung erfüllt, dass benachbarten Knoten nicht dieselbe Farbe (Element) von C zugewiesen (d. h. auf sie abgebildet) wird. Eine Färbung, die diese Kriterien nicht erfüllt, wird als unangemessene Färbung bezeichnet. Dies sind die Anforderungen; da wir es jedoch fast immer mit richtigen Färbungen zu tun haben werden, ist es praktischer, das Wort „richtig“ zu streichen und uns darauf zu einigen, dass wir, wenn wir von „Färbungen“ eines Graphen sprechen, „richtige Färbungen“ meinen, sofern nicht anders angegeben.