{"entities":{"Q919008":{"pageid":920856,"ns":120,"title":"Item:Q919008","lastrevid":65379918,"modified":"2026-04-12T02:11:38Z","type":"item","id":"Q919008","labels":{"en":{"language":"en","value":"Nonexistence of certain 4-critical graphs of order 12"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4158659"}},"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":"Q919008$0F1164AF-175A-4212-8392-BFC16606BBCC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af26fa96bb3b71dd06007548fe6fee7a93407c09","datavalue":{"value":{"text":"Nonexistence of certain 4-critical graphs of order 12","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q919008$63925B34-42C3-4AFD-B269-8D2EE5006DC5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af7664ef618df83a9d7845f6c2eb9447cecf348e","datavalue":{"value":"0706.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919008$AF2E5CD1-ED6F-4111-B91A-60C8A1D32AB1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3892dce641e5f7f85ae8d827a514bd170a5b114","datavalue":{"value":{"entity-type":"item","numeric-id":919007,"id":"Q919007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919008$1FCBAA3E-3A4C-4B44-B1EC-DE6105B66FB2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6c13805eb53dbd00bf0343bc22d19b4be9e16872","datavalue":{"value":{"entity-type":"item","numeric-id":187667,"id":"Q187667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919008$98C531BD-F7D6-406F-B737-D4F8C98EB90A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q919008$C5B70728-E3DC-4EC0-B675-949640432B80","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18cb35bc25edc5c092071041af6dde3a42c8778d","datavalue":{"value":"The well-known Vizing theorem [\\textit{V. G. Vizing}, Diskretn. Analiz. 3, 25-30 (1964)], states that chromatic index \\(\\chi '(G)\\) of a simple graph G with maximum vertex degree \\(\\rho\\) is equal either to \\(\\rho\\) or to \\(\\rho +1\\). A connected graph G with maximum degree \\(\\rho\\) is said to be \\(\\rho\\)- critical if \\(\\chi '(G)=\\rho +1\\) and elimination of any edge lowers its chromatic number.    The important question of the existence of critical graphs with a given even number of nodes remains unsolved. A partial solution has been provided. Here we consider graphs of order 12 with maximum degree 4 and prove following Theorem: There are no 4-critical graphs with partition \\(2^ 44^ 8\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q919008$66BDE587-6DF4-49AD-A0B0-BD469F170850","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919008$030C9072-28DF-4B93-AAC3-2D94485CBD30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919008$DBFEB1E3-8FBE-431E-96AE-AF250D473CEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"21060f0b04775ebbad5b3d8939a93a0e8ef9aa95","datavalue":{"value":"4158659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919008$DF8C49FB-88F2-4A00-9594-669855AB5735","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd61796560ff3e7a14b1216a85cef383fb56549f","datavalue":{"value":"Vizing theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q919008$705F9FEE-DB0C-4310-8A27-5A10952F10F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q919008$92D3486F-9FD0-49DC-A5F1-AD7A03A12A54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q919008$0B573FEF-7FC9-4C79-836B-78D09FB08CE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q919008$6C03F169-6C3C-45ED-B48A-419DA6BACBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bc9b8064a611e5192947becc4d61260f5d72601","datavalue":{"value":"4- critical graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q919008$B2025CE6-7255-4C2C-B4A7-67AC4F49024B","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":"Q919008$23A2663A-0C4B-4721-912D-22D3CC57D274","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"711d3b81ac0056de56cdf777f4c5a2d19b02bda8","datavalue":{"value":{"entity-type":"item","numeric-id":1894759,"id":"Q1894759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30ec8f97523ecf49a25375d149b24a2a89dba0e4","datavalue":{"value":{"amount":"+0.9194633364677428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919008$EB271C79-B75E-462C-81F3-A7519F6F97B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bf64ef06c89ddf491799787fc97e55db9b3270d","datavalue":{"value":{"entity-type":"item","numeric-id":4693341,"id":"Q4693341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30ec8f97523ecf49a25375d149b24a2a89dba0e4","datavalue":{"value":{"amount":"+0.9194633364677428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919008$35E48086-DC77-4600-A658-A87AECA4C3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cf185e170d9b4fd62dd3a6a0a13c20d673ee4bb","datavalue":{"value":{"entity-type":"item","numeric-id":4713915,"id":"Q4713915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8046e72d2347945c2d66a71014dc97199e2dcc6","datavalue":{"value":{"amount":"+0.9019879698753356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919008$DF2A4DC2-B3AD-4973-A482-2A162378D31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95a6db24cb2ecb75d95e59809fff863cfc349922","datavalue":{"value":{"entity-type":"item","numeric-id":1277310,"id":"Q1277310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a7110ba2ae86a47f54ab6ba2ddefd3da6828220","datavalue":{"value":{"amount":"+0.8515891432762146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919008$3D517181-5E23-4BCD-B893-7ADBFD380E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a5c56143bf886db9fd7901f16460aa33f173125","datavalue":{"value":{"entity-type":"item","numeric-id":1043537,"id":"Q1043537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a7110ba2ae86a47f54ab6ba2ddefd3da6828220","datavalue":{"value":{"amount":"+0.8515891432762146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919008$2D8D6659-B101-46AC-B223-6C35AB2A7A93","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonexistence of certain 4-critical graphs of order 12","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonexistence_of_certain_4-critical_graphs_of_order_12"}}}}}