{"entities":{"Q1318798":{"pageid":1329548,"ns":120,"title":"Item:Q1318798","lastrevid":67163103,"modified":"2026-04-12T15:43:15Z","type":"item","id":"Q1318798","labels":{"en":{"language":"en","value":"The total chromatic number of regular graphs whose complement is bipartite"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 540928"}},"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":"Q1318798$5F9B2B6F-CBC3-4FB5-9E6E-DE7CB9CA7DE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"09bb6daabc6df2770ecf287bf35644f86ec33524","datavalue":{"value":{"text":"The total chromatic number of regular graphs whose complement is bipartite","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1318798$ECEB72A8-BEAF-479D-B76D-4A1DA4F033AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba8f80494f8a613cdab5a184739405d832c26e3a","datavalue":{"value":"0794.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1318798$4CF1F347-A63D-485A-A403-DBF7EEDCA573","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45f1dff85a4d41ba3f5c3d144b91f0f4ec1e1f28","datavalue":{"value":"10.1016/0012-365X(94)90255-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1318798$4CE5ADC6-05C2-48CB-9D25-11903709F5A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$BDB2F2D6-0F29-44ED-8786-AD8C64AADCD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2eb4327a643e96182550341c5d2d3e1446617b8e","datavalue":{"value":{"time":"+1994-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1318798$A9DF3212-CA81-404E-AD86-CB0F0FC15600","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e98d0b7e4b558b219e9fcf627debb95b1bc05e1b","datavalue":{"value":"Given a graph \\(G= (V,E)\\), a total coloring of \\(G\\) is an assignment of colors to the elements of \\(V\\cup E\\) in such a way that no two adjacent or incident elements receive the same color. The total chromatic number \\(\\chi''(G)\\) is the least number of colors in a total coloring of \\(G\\). There is an almost 30-years-old conjecture that for a simple graph \\(G\\) we have \\(\\Delta+ 1\\leq \\chi''(G)\\leq \\Delta+ 2\\), where \\(\\Delta\\) is the maximum vertex degree of \\(G\\). If \\(\\chi''(G)= \\Delta+ 1\\) then graph \\(G\\) is type 1 and if \\(\\chi''(G)= \\Delta+ 2\\) then \\(G\\) is type 2. Deciding the type of \\(G\\) is NP-complete. In the paper the authors prove the following theorem:   Let \\(G\\) be a regular simple graph of even order \\(2n\\geq 6\\) such that \\(\\overline G\\) is bipartite. Then \\(G\\) is of type 1 if and only if: (i) \\(G\\neq K_{2n}\\) and (ii) \\(\\overline G\\neq K_{n,n}\\) when \\(n\\) is even.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$B9261916-1888-4B7F-A5B8-D80019D779E5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$0CD85D14-962E-453E-A377-85A95F4F0203","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1318798$0A1C0E86-80F1-4686-A524-BE1E8C193728","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"376a1181330de9580cf20e192589d401acd593ac","datavalue":{"value":"540928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1318798$82BB2585-50E3-4EC8-AE1F-779004A5DE87","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da89ad1af6a79bb08d8b0b36204e01323fa3c5ee","datavalue":{"value":"1-factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$7C65987C-C1EC-4DC0-9BCE-5F69BA7F2638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10a5749cf250aeb831bc95ff6c67868b31bb5c8c","datavalue":{"value":"total coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$8FEC749F-1074-4692-80BF-932A3523BCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"917eb44fe6d809e0bc9389e0c20d8b3e6f0da35b","datavalue":{"value":"total chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$3F2C3EB1-03BC-4A52-BB69-7C13338A4672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6505e3a410a92a048ba72a3c66ad44d736aa18e0","datavalue":{"value":"simple graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$19270A7A-A098-4C02-B294-06347C878AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8922343abb2e01d0050c8415bee74ccfda909cb9","datavalue":{"value":"maximum vertex degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$3E35690A-A0E4-4B8E-A22C-CED21FEFABC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3a2d99dd366e12ee8fd608e27922f0828010815","datavalue":{"value":"type","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$D4C25CEE-5C1F-4A36-9F7B-7424BAF7802D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$488A06AA-5096-4DEE-9BBF-4E9FDBC8EEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42104ac6a2a39d8f86a7cc32ce4b7d6d031d8fca","datavalue":{"value":"regular simple graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$61EB488E-CDDC-4C90-8793-BD0116A390F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58d98a8e8a82d5ced11d99fa8f7f4a8fc50c0d4e","datavalue":{"value":"bipartite","type":"string"},"datatype":"string"},"type":"statement","id":"Q1318798$1BC513D1-2D2A-43ED-8911-E46021DB0D43","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"44f80e35ea10d056d2c61cfad297a8e0f8eeda6a","datavalue":{"value":{"entity-type":"item","numeric-id":960931,"id":"Q960931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$BB3DCBB7-96E9-4795-9B72-753B4805EEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fed0fe195c7c30cec1ec29d1ddd1134cd27f289","datavalue":{"value":{"entity-type":"item","numeric-id":590704,"id":"Q590704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$806DC335-907A-4B36-9B03-C342974BC954","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":"Q1318798$56D8AFA4-CEFD-4F00-AD87-FB36F3F72DDB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a18decd282151f0c50f68615d322424f0bc10cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5621372,"id":"Q5621372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$5089454F-72E1-4A7F-BEC2-5A3F2F19D180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb1fbc07724c83ce3aa801e461f75221119bad05","datavalue":{"value":{"entity-type":"item","numeric-id":3832589,"id":"Q3832589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$E2E2E203-168A-4F60-9B36-6B360AE02898","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05e7d326cc6d8f2c226bea7c9f6127474db39f15","datavalue":{"value":{"entity-type":"item","numeric-id":4009489,"id":"Q4009489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$26322C5C-228D-4063-9525-18AFFD6465BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89b741060f588de7a4ea9a3a26f7dfabdb68fc9d","datavalue":{"value":{"entity-type":"item","numeric-id":3984519,"id":"Q3984519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$2A71CBFB-551D-4916-97D0-5F7897A251B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770841483c24d9410a5dde804415d5f3ae756334","datavalue":{"value":{"entity-type":"item","numeric-id":3266934,"id":"Q3266934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$89C09FF3-A3F4-452B-8E93-A2A2AABE27DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10c35c8dd9144d24fbde511328d088386877a678","datavalue":{"value":{"entity-type":"item","numeric-id":1109776,"id":"Q1109776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$EA54C5FC-A699-48F3-BC94-DCF3B7C7F648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"602ee18d4f8112cece600c3648f044b0d41b89c9","datavalue":{"value":{"entity-type":"item","numeric-id":686483,"id":"Q686483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$D8195ABF-13FF-4147-A4B2-D5232E84F15E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f40ac77788ea4552d1648038e3f98605a9ae8989","datavalue":{"value":{"entity-type":"item","numeric-id":1186314,"id":"Q1186314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$D05E67F2-103B-4313-B4C7-460BAE79CD38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3ad8f1aa08a3f5d922f33d16ad0559fee339c","datavalue":{"value":{"entity-type":"item","numeric-id":750449,"id":"Q750449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$36ACA2C1-1D3A-40E4-80EE-7B475ACBCC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25689778c830e23fb04d27fc7257d49f1890e164","datavalue":{"value":{"entity-type":"item","numeric-id":686156,"id":"Q686156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$9905BBAB-CD70-44B1-AEA5-176A4CC4DD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae812f45eee83390449dec4a9402449eda59fada","datavalue":{"value":{"entity-type":"item","numeric-id":3987044,"id":"Q3987044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$F90C1BE6-2774-4959-B9E5-A9158C41228C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0b70cd279cf9b80bd399720676554acfb6dc677","datavalue":{"value":{"entity-type":"item","numeric-id":2277479,"id":"Q2277479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$B3033BE9-EC3F-4C34-B928-20DAA6DB8819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd8a1e7c7aae77afda3dc242c9a9d4c2ad31ecb8","datavalue":{"value":{"entity-type":"item","numeric-id":5799732,"id":"Q5799732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$912D1A78-A73A-4C23-9624-56B9B4455EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f522c8b08e8d38892906f8e283d82e9c72770b38","datavalue":{"value":{"entity-type":"item","numeric-id":1259607,"id":"Q1259607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$B042225A-57EB-4C09-88B6-E3B8EB2875F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9a77b50c698d35e0bfbd498c866f480eb9f390","datavalue":{"value":{"entity-type":"item","numeric-id":5591387,"id":"Q5591387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$7E4FAD28-CEC9-426F-8FB4-C0AF5CC9EF52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d7689ee794d05f267735d01d099a85da834d533","datavalue":{"value":{"entity-type":"item","numeric-id":5564127,"id":"Q5564127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1318798$22771227-D42B-4626-93DA-E7A05F43255F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"118f6b8daade2e23cbf5f881371d2fd7ffc3a3ea","datavalue":{"value":{"entity-type":"item","numeric-id":3809815,"id":"Q3809815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8997e26c51ed7ea57241926b0e6c8b75f2879691","datavalue":{"value":{"amount":"+0.8649470806121826","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":"Q1318798$537E4B81-96D6-495C-831A-95634B57632A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dedb7b10c20f6a59d7302bd558eb8a0fb736c8f6","datavalue":{"value":{"entity-type":"item","numeric-id":1297471,"id":"Q1297471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ae05ff774fedde65fd01a43f3c4d9c00c3eb7d7","datavalue":{"value":{"amount":"+0.8621429800987244","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":"Q1318798$AD565379-75EC-4C69-8C86-B4D7A74C9A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9978034d2cea4d6690197816b3aa808a39b5336","datavalue":{"value":{"entity-type":"item","numeric-id":1918537,"id":"Q1918537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ae05ff774fedde65fd01a43f3c4d9c00c3eb7d7","datavalue":{"value":{"amount":"+0.8621429800987244","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":"Q1318798$BD04A1C1-CC26-4098-A924-830CCE76AB00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffd1f18dc539717e01cd7ccdad856bc54327b965","datavalue":{"value":{"entity-type":"item","numeric-id":3832589,"id":"Q3832589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33c4cbf1b6b8d45c15176be671274eede3f262cd","datavalue":{"value":{"amount":"+0.8620564937591553","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":"Q1318798$B48E6CB2-CA3C-47B7-92C7-455733B71517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfa53f28bc88ab3b89c3c5199ae7ea43c6cf0563","datavalue":{"value":{"entity-type":"item","numeric-id":4376493,"id":"Q4376493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d700a464867e8d8b27fe92898d216745faa90e","datavalue":{"value":{"amount":"+0.8574205040931702","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":"Q1318798$8D84EF39-D5E0-4277-8091-58EFBEFAE8AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The total chromatic number of regular graphs whose complement is bipartite","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_total_chromatic_number_of_regular_graphs_whose_complement_is_bipartite"}}}}}