{"entities":{"Q5893005":{"pageid":7931076,"ns":120,"title":"Item:Q5893005","lastrevid":41300448,"modified":"2025-04-28T13:07:30Z","type":"item","id":"Q5893005","labels":{"en":{"language":"en","value":"The coloring of graphs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2550900"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893005$3F37E9BB-9FB3-4247-95E4-2454DF76CFA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"01ee5711f7f9418447779fe2a169e8780fdc5e86","datavalue":{"value":{"text":"The coloring of graphs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5893005$CA41FEFB-B85A-47CD-9A6F-94CF2A07D6E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"20d52cdce785e5111e1360b0e5f041758001ee1a","datavalue":{"value":"58.0606.01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893005$24E5C2DA-B086-4F0E-965D-FF92A6CD1DC3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fc7d08913c99dc077b318f45531657020f591e8","datavalue":{"value":"10.2307/1968214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893005$0A1C669C-A95A-4CEB-8FE2-CC5661AD282B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893005$8F873C4E-9768-455E-903B-45DAB0D2F528","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7bbb53abe68aac0eeb25dacc2ea1a7274c90a69a","datavalue":{"value":{"time":"+1932-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5893005$ADC03A01-266A-4C19-AB90-9737828BC1E8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"088abfe88fbec6e72bf651d4a8971a0e603e2435","datavalue":{"value":"Ausgehend von der Formel (**) des vorangehenden Referats wird die \\textit{Birkhoff}sche Formel f\u00fcr die Anzahl der zul\u00e4ssigen F\u00e4rbungen 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\u00e4nglich zu machen.  Der Graph \\(G\\) bisitze keine Schlingen, habe \\(V\\) Knotenpunkte, \\(P\\) zusammenh\u00e4ngende Bestandteile und \\(E\\) Kanten, sei also vom Range \\(R=V-P\\) und der Nullit\u00e4t \\(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\u00fcr } i<0 \\text{ oder } j<0 \\text{ oder } i>R \\text{ oder } j>N;\\end{gathered}  \\]  Abz\u00e4hlung der Teilgraphen von \\(G\\) mit \\(i\\) Kanten liefert die Identit\u00e4ten  \\[  m_{i0}+m_{i-1,1}+\\cdots +m_{0i}=\\binom {E}{i}\\quad (i=0,1,\\dots,E). \\]  Die Deutung mit Hilfe der unvollst\u00e4ndigen Kreise (vorstehendes Referat) ergibt:  \\[ (-1)^i m_i \\begin{cases} >0 & \\text{ f\u00fcr } 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\u00fcr \\(E>0\\) bzw. \\(E=0\\). Ferner f\u00fcr einen Kreis \\(G\\):  \\[ M(\\lambda )=(\\lambda -1)^E +(-1)^E (\\lambda -1). \\]   Von den beiden Umformungen der Formel (**), die Verf. zun\u00e4chst 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\u00e4ndigen Kreisen mit zusammen \\(k\\) Kanten bedeuten.  Zur Bestimmung der \\(m_{ij}\\) kann man sich indessen auch auf die Abz\u00e4hlung der nicht-separablen Teilgraphen von \\(G\\) beschr\u00e4nken. Verf. zeigt n\u00e4mlich: Sind \\(T_1, T_2,\\dots \\) die verschiedenen (d. h. nicht kongruenten) Typen nicht-separabler Graphen in irgend einer festen Reihenfolge, und enth\u00e4lt \\(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\u00e4ngen. Verf. kann auch noch genauere Aussagen dar\u00fcber machen, welche Typen \\(T_l\\) (nach Rang und Nullit\u00e4t klassifiziert) zu einem gegebenen \\(m_{ij}\\) einen Beitrag liefern k\u00f6nnen; f\u00fcr 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\u00fcr 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\u00fcr 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 )\\) \u00fcber, 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\u00fcr Systeme \\(m, f\\) mit einem und mit zwei Indices untersucht.) Man erh\u00e4lt 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\u00fcr  \\[ 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\u00df\\ auch die \\(f_{ij}\\) Polynome in den \\(N_l\\) ohne konstantes Glied mit von \\(G\\) unabh\u00e4ngigen Koeffizienten sind.  Um weiter einfach rechnen zu k\u00f6nnen, 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\u00fcltig 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\u00fcr \\(k\\neq l\\) bilden eine Basis des Moduls der verallgemeinerten Graphen. Hieraus folgt, da\u00df\\ 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\u00fcr \\(p\\leq i\\), \\(q\\leq j\\) kennt, so kann man vermittels der Transformationsformeln \\(m_{ij}\\) berechnen. \u00dcbrigens sind die \\(m_{ij}\\) - abgesehen von den \\(m_{i0}\\) mit \\(i \\neq 1\\) -, ebenso auch die \\(f_{ij}\\) voneinander unabh\u00e4ngig in dem Sinne, da\u00df\\ ein Polynom in den \\(m_{ij}\\) oder \\(f_{ij}\\), das f\u00fcr alle Graphen oder auch nur f\u00fcr alle nicht-separablen Graphen verschwindet, identisch null ist.  Verf. zeigt schlie\u00dflich noch f\u00fcr die niedrigsten Werte der Indices, wie nach diesen Bemerkungen die \\(f_{ij}\\), \\(m_{ij}\\) und \\(m_i\\) als Polynome in den \\(N_l\\) tats\u00e4chlich berechnet werden k\u00f6nnen, insbesondere auch f\u00fcr die den regul\u00e4ren Karten entsprechenden Graphen. F\u00fcr die Dodekaedereinteilung der Kugelfl\u00e4che 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\u00e4hnt sei hier noch die, wie ein Beispiel zeigt, tats\u00e4chlich verallgemeinerte Vierfarbenvermutung: Wenn ein Graph \\(G\\) einen Dualen \\(G'\\) besitzt (was mit der M\u00f6glichkeit der Einbettung in die Ebene gleichbedeutend ist; vgl. die nachstehend besprochene Arbeit), so gilt f\u00fcr die \\(m_{ij}\\) der beiden Graphen:  \\[ m'_{ij}=m_{R-j, N-i}. \\]  Die Vierfarbenvermutung ist in der Vermutung enthalten, da\u00df\\ f\u00fcr jeden Graphen \\(G\\), zu dem ein \\(G'\\) existiert, dessen \\(m'_{ij}\\) zu den \\(m_{ij}\\) in der obigen Beziehung stehen, \\(M(4)>0\\) ist.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5893005$B6445D23-5A70-4B3B-993D-3AB5187A3446","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a81c0e9c54e989c2121578c6664dab004f91225","datavalue":{"value":"2550900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893005$55423B51-2C3D-4377-A625-50C778EEB296","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"cf8629f711c4cc410b24e5d8a662ac03c92ba450","datavalue":{"value":"Q33738429","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893005$535B4AE9-D73F-4408-9C4C-DB338C322BD0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"144a6eebf639ea543bd03fa2e7064384b1e7bf2e","datavalue":{"value":{"entity-type":"item","numeric-id":593326,"id":"Q593326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893005$D63A6002-27F5-4625-AEDA-1229C672E382","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893005$B4EE0153-BC42-48A2-9D21-561BA1746E28","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"97d6339e286cf8380c037f651e3307047a514ba8","datavalue":{"value":"https://doi.org/10.2307/1968214","type":"string"},"datatype":"url"},"type":"statement","id":"Q5893005$970344F7-7496-4C49-9630-88453E3D37D6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0b7311f2a4e27d19319c9ef840f6d5a8b7a0838a","datavalue":{"value":"W2332615042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893005$26FF97FD-CC76-474B-B700-D8F8A64E784C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d31ddd2a071b5cbac90da3e8f29d3f22b0ba0eba","datavalue":{"value":{"entity-type":"item","numeric-id":6480746,"id":"Q6480746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893005$F39AD6CF-DD45-465E-BE6F-665E7F78F1B7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5893005","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5893005"}}}}}