×

zbMATH — the first resource for mathematics

The coloring of graphs. (English) JFM 58.0606.01
Ausgehend von der Formel (**) des vorangehenden Referats wird die Birkhoffsche Formel für die Anzahl der zulässigen Färbungen eines Graphen - gelegentlich unter Benutzung formal-logischer Entwicklungen (vgl. Verf., 1933; F. d. M. \(56_{\text{I}}\), 51) - weiter umgeformt, mit dem Ziel, \(M(\lambda )\) der numerischen Berechnung zugänglich zu machen.
Der Graph \(G\) bisitze keine Schlingen, habe \(V\) Knotenpunkte, \(P\) zusammenhängende Bestandteile und \(E\) Kanten, sei also vom Range \(R=V-P\) und der Nullität \(N=E-R\). Aus der Definition der \(m_{ij}\) folgt unmittelbar \[ \begin{gathered} m_{00}=1,\quad m_{10}=E,\quad m_{RN}=1,\\ m_{ij}=0\text{ für } i<0 \text{ oder } j<0 \text{ oder } i>R \text{ oder } j>N;\end{gathered} \] Abzählung der Teilgraphen von \(G\) mit \(i\) Kanten liefert die Identitäten \[ m_{i0}+m_{i-1,1}+\cdots +m_{0i}=\binom {E}{i}\quad (i=0,1,\dots,E). \] Die Deutung mit Hilfe der unvollständigen Kreise (vorstehendes Referat) ergibt: \[ (-1)^i m_i \begin{cases} >0 & \text{ für } i=0,1,\dots,R,\\ =0 & \text{ sonst.} \end{cases} \] Hieraus ergeben sich formal die nach Definition evidenten Formeln \(M(0)=0; M(1)=0\) oder \(1\) für \(E>0\) bzw. \(E=0\). Ferner für einen Kreis \(G\): \[ M(\lambda )=(\lambda -1)^E +(-1)^E (\lambda -1). \]
Von den beiden Umformungen der Formel (**), die Verf. zunächst ableitet, sei hier eine als Beispiel angegeben: \[ M(\lambda )=\lambda ^{V-E} \sum (-1)^i \alpha _i (\lambda -1)^{E-i}\quad \text{mit}\quad \alpha _i =\sum (-1)^k \alpha _{ik}, \] wo die \(\alpha _{ik}\) die Anzahlen von Systemen von \(i\) unvollständigen Kreisen mit zusammen \(k\) Kanten bedeuten.
Zur Bestimmung der \(m_{ij}\) kann man sich indessen auch auf die Abzählung der nicht-separablen Teilgraphen von \(G\) beschränken. Verf. zeigt nämlich: Sind \(T_1, T_2,\dots \) die verschiedenen (d. h. nicht kongruenten) Typen nicht-separabler Graphen in irgend einer festen Reihenfolge, und enthält \(G\) \(N_l\) Teilgraphen vom Typus \(T_l\), so ist jedes \(m_{ij}\) eindeutig als Polynom in den \(N_l\) ohne konstantes Glied darstellbar, wobei die Koeffizienten nicht von \(G\) abhängen. Verf. kann auch noch genauere Aussagen darüber machen, welche Typen \(T_l\) (nach Rang und Nullität klassifiziert) zu einem gegebenen \(m_{ij}\) einen Beitrag liefern können; für die Einzelheiten dieser Untersuchung sei auf die Arbeit selbst verwiesen.
Sind \(G_1, G_2\) zwei zueinander fremde Graphen, \(G_1+G_2\) ihre Summe, so gilt für die \(m_{ij}\) \[ \begin{gathered} m_{ij}(G_1+G_2)=\sum _{p,q} m_{pq}(G_1)m_{i-p, j-q}(G_2),\\ m_{00}(G)=1\quad \text{für alle }G.\end{gathered} \] Verf. geht nun durch eine geeignete Transformation von den \(m_{ij} (i,j=0,1,\dots )\) zu Zahlen \(f_{ij} (i,j=0,1,\dots )\) über, die die einfachere Additionsregel \[ f_{ij}(G_1+G_2)=f_{ij}(G_1)+f_{ij}(G_2) \] befolgen. (Derartige Transformationen werden ohne Bezugnahme auf die Graphentheorie für Systeme \(m, f\) mit einem und mit zwei Indices untersucht.) Man erhält eine solche Transformation, indem man jedem Graphen \(G\) formale Potenzreihen \[ F_G(x,y)=\sum _{i,j=1}^{\infty }f_{ij}(G)x^iy^j,\quad M_G(x,y)=\sum _{i,j=0}^{\infty }m_{ij}(G)x^iy^j \] zuordnet und die \(m\) aus den \(f\) bzw. die \(f\) aus den \(m\) als Koeffizienten der formalen Reihenentwicklungen für \[ e^{F_G(x,y)}=M_G(x,y)\quad \text{bzw.}\quad \log M_G(x,y)=F_G(x,y) \] bestimmt. Die Transformationsformeln haben folgende Gestalt: \[ f_{ij}=m_{ij}+P_{ij}(m_{pq}),\quad m_{ij}=f_{ij}+Q_{ij}(f_{pq}), \] wobei die \(P, Q\) Polynome ohne konstante und lineare Glieder in den \(m_{pq}\) bzw. \(f_{pq}\) mit \(p\leq i\), \(q\leq j\) und \(p, q \neq i,j\) sind. Mit dieser Eigenschaft als Zusatzforderung ist die engegebene Transformation die einzige. Die spezielle Gestalt der Transormationsformeln bedingt, daß auch die \(f_{ij}\) Polynome in den \(N_l\) ohne konstantes Glied mit von \(G\) unabhängigen Koeffizienten sind.
Um weiter einfach rechnen zu können, verallgemeinert Verf. den Begriff des Graphen: Ein verallgemeinerter Graph ist einfach ein System ganzer Zahlen \(N_l\), die angeben, wie oft der Typ \(T_l\) in dem verallgemeinerten Graphen als Teilgraph auftritt, gleichgültig ob diesen Zahlen ein wirklicher Graph entspricht oder nicht. Die \(f_{ij}\) und \(m_{ij}\) sind dann durch die Polynome in den \(N_l\) bestimmt. Man kann verallgemeinerte Graphen durch Linearkombination der entsprechenden \(N_l\) linear kombinieren, wobei sich die \(f_{ij}\) ebenfalls linear kombinieren. Jeder verallgemeinerte Graph ist eine Linearkombination von wirklichen Graphen. Die Graphen \(G_l\) mit \(N_l=1\), \(N_k=0\) für \(k\neq l\) bilden eine Basis des Moduls der verallgemeinerten Graphen. Hieraus folgt, daß die \(f_{ij}\) linear und homogen in den \(N_l\) sind, und zwar sind sie gerade die linearen Bestandteile der \(m_{ij}\). Wenn man nun die linearen Bestandteile \(f_{pq}\) von \(m_{pq}\) für \(p\leq i\), \(q\leq j\) kennt, so kann man vermittels der Transformationsformeln \(m_{ij}\) berechnen. Übrigens sind die \(m_{ij}\) - abgesehen von den \(m_{i0}\) mit \(i \neq 1\) -, ebenso auch die \(f_{ij}\) voneinander unabhängig in dem Sinne, daß ein Polynom in den \(m_{ij}\) oder \(f_{ij}\), das für alle Graphen oder auch nur für alle nicht-separablen Graphen verschwindet, identisch null ist.
Verf. zeigt schließlich noch für die niedrigsten Werte der Indices, wie nach diesen Bemerkungen die \(f_{ij}\), \(m_{ij}\) und \(m_i\) als Polynome in den \(N_l\) tatsächlich berechnet werden können, insbesondere auch für die den regulären Karten entsprechenden Graphen. Für die Dodekaedereinteilung der Kugelfläche gibt er an: \[ \begin{aligned} M(\lambda )=\lambda (\lambda -1)(\lambda -2)(\lambda -3)(\lambda ^8-24& \lambda ^7+260\lambda ^6-1670\lambda ^5+6999\lambda ^4\\ &-19698\lambda ^3+36408\lambda ^2-40240\lambda +20170). \end{aligned} \] Erwähnt sei hier noch die, wie ein Beispiel zeigt, tatsächlich verallgemeinerte Vierfarbenvermutung: Wenn ein Graph \(G\) einen Dualen \(G'\) besitzt (was mit der Möglichkeit der Einbettung in die Ebene gleichbedeutend ist; vgl. die nachstehend besprochene Arbeit), so gilt für die \(m_{ij}\) der beiden Graphen: \[ m'_{ij}=m_{R-j, N-i}. \] Die Vierfarbenvermutung ist in der Vermutung enthalten, daß für jeden Graphen \(G\), zu dem ein \(G'\) existiert, dessen \(m'_{ij}\) zu den \(m_{ij}\) in der obigen Beziehung stehen, \(M(4)>0\) ist.

PDF BibTeX XML Cite
Full Text: DOI