{"entities":{"Q396886":{"pageid":398653,"ns":120,"title":"Item:Q396886","lastrevid":61622169,"modified":"2026-04-11T00:32:32Z","type":"item","id":"Q396886","labels":{"en":{"language":"en","value":"Nordhaus-Gaddum theorem for the distinguishing chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330318"}},"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":"Q396886$106CFBFB-11DA-4E6C-84C0-D3C204B80CF5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d22c1e82a37bb6df3b9be39c829f51d31cf01a0e","datavalue":{"value":{"text":"Nordhaus-Gaddum theorem for the distinguishing chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q396886$F9DE946C-BF3E-451A-A40B-C7A53DB0042E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ecde1142e9e9a0b72826814392855239616703c2","datavalue":{"value":"1298.05112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396886$EF4A4CC8-A9CE-43B1-88E6-444E65FF21A7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a80f0a30c34568b1594b2aaace08fe6b51a1e6b","datavalue":{"value":{"entity-type":"item","numeric-id":234314,"id":"Q234314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$1C569DBC-F928-44DB-BC83-9547CFC4AAAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d32bdb43352779c472e08e65787c883d867f4a6","datavalue":{"value":{"entity-type":"item","numeric-id":251908,"id":"Q251908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$1F507931-E72B-47BA-8FD6-28F40FF9C30B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$5D310374-44D2-4A9A-9CBF-B4E76524C96F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q396886$5B843C39-B8A4-4114-96C7-3D63B6F6622B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"24f54323d68d597a905c9b9a7a61ab79a2494b99","datavalue":{"value":"https://arxiv.org/abs/1203.5765","type":"string"},"datatype":"url"},"type":"statement","id":"Q396886$59EAD5E3-CC8C-43BB-B02A-A02C0B2B76F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"98da3deb0b975b25024ead543a47e137ba666e4c","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p46","type":"string"},"datatype":"url"},"type":"statement","id":"Q396886$7FB8972C-6299-4A72-9690-33752E36FAC4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"06c0c3c3ae9d2ea1a6b54ddc5c366cc50986e489","datavalue":{"value":"Summary: \\textit{E. A. Nordhaus} and \\textit{J. W. Gaddum} [Am. Math. Mon. 63, 175--177 (1956; Zbl 0070.18503)] proved for any graph \\(G\\), that \\(\\chi(G) + \\chi(\\overline{G}) \\leq n + 1\\), where \\(\\chi\\) is the chromatic number and \\(n=|V(G)|\\). \\textit{H.-J. Finck} [in: Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 99--113 (1968; Zbl 0157.55201)] characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NG-graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of NG-graphs. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number. For any graph \\(G, \\chi_D(G) +\\chi_D(\\overline{G})\\leq n+D(G)\\). We call the set of graphs that satisfy equality in this bound NGD-graphs, and characterize the set of graphs that are simultaneously NG-graphs and NGD-graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q396886$04F3A9CF-09EF-4141-AFA4-8EA74B8B05AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396886$E396D0D0-6DC8-4C69-ACD9-F6F7D82FF9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396886$20B05004-3D69-4B72-B9C2-00D487FB6092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396886$E2F400A2-4947-42D2-9136-60A4FE43C726","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2411e0203e0d80ec0aa3aad0e43de9f76754c9d7","datavalue":{"value":"6330318","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396886$1EF1B876-3B60-426E-8D6F-61B744C5D266","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q396886$13771BA0-94E7-4212-A240-AFC93B1E6D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c0140de3f08eb78ec7999a29727e9d8a4f3a187","datavalue":{"value":"distinguishing chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q396886$F9C5A112-89E4-470A-A36B-14558733F741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c3309b9583078c7b65b2a1d8e8e19cdecde7d0f","datavalue":{"value":"Nordhaus-Gaddum theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q396886$4A12C6D7-6DA1-415D-8E67-7A410EF06F45","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":"Q396886$1C31BC91-6134-4449-A1E8-A78CA69FA5AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"151f15a8b698ad73a2a186b87f481f657a6e7374","datavalue":{"value":{"entity-type":"item","numeric-id":3419706,"id":"Q3419706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$CE587E55-579D-4E86-AD11-78A179C64E3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9234f0e63bf5a06d1fb5cac8ee4d51f04190a4c4","datavalue":{"value":{"entity-type":"item","numeric-id":1918875,"id":"Q1918875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$15AF7575-7225-4E58-8446-84860CB794F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46bd59c7929f172c46f40d302bb7c90dbca12884","datavalue":{"value":{"entity-type":"item","numeric-id":3648500,"id":"Q3648500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$C12D7408-7E75-47A4-B374-AAF6E414E63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"925b7d5c0ce9dcd2bdba9404aa855c27af3f2388","datavalue":{"value":{"entity-type":"item","numeric-id":3169264,"id":"Q3169264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$53ACF0B2-93A2-44B6-9500-8E8320038DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c0858247d908dd5e3fd01d4d9c863c992769d5","datavalue":{"value":{"entity-type":"item","numeric-id":1953399,"id":"Q1953399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$37F4C7D3-B02F-4435-8380-54CF33CDC1AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b268f1864fbdc90dceea7e74710ad96ba322a9","datavalue":{"value":{"entity-type":"item","numeric-id":1044994,"id":"Q1044994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$82B3E16F-EF9E-404B-A6B3-B34C5F13353F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af7ef0d2104c6fdf226b9a03410043120e5aa415","datavalue":{"value":{"entity-type":"item","numeric-id":3084214,"id":"Q3084214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$AB9AAC58-8DF9-4C7A-B6FD-CCFB861A7D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e64f43320f985ffdadca489263dbf92edb05478","datavalue":{"value":{"entity-type":"item","numeric-id":2380243,"id":"Q2380243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$CD25920F-106B-439C-BD59-878A2F4410D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad054570a463afcdd43da51b1cf712b854fcb25","datavalue":{"value":{"entity-type":"item","numeric-id":815210,"id":"Q815210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$2F3894C9-CBB2-41C2-9642-2590D84542A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d860188b1476d2fbdafa8166d7cccb5b67f06e10","datavalue":{"value":{"entity-type":"item","numeric-id":3119062,"id":"Q3119062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$783284B2-B2DD-4D2C-862E-2C7912C648DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f41b6467cad2e7b26a10fea83fa6149b1159c89","datavalue":{"value":{"entity-type":"item","numeric-id":5540282,"id":"Q5540282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$11B0143A-D2D0-421A-A4C4-552BBF108CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$2D174859-1044-44A7-91C6-087CD46A07D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e09c606c496e90c08c7ed87c9fa59fa93105e670","datavalue":{"value":{"entity-type":"item","numeric-id":2427541,"id":"Q2427541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$E163E5A0-1212-4BF9-8D67-2411A8DD28EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df678bbdd343ff667491f6185324cd2b60532e67","datavalue":{"value":{"entity-type":"item","numeric-id":764823,"id":"Q764823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$BA10C3D2-239A-4F52-9C0E-D7B735DE923E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf5b8da49d0437a0ece39762a871932ab35cee0d","datavalue":{"value":{"entity-type":"item","numeric-id":2380452,"id":"Q2380452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$2440DD35-0EF2-4259-83F1-FAB793155DEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62ef5d210732bda8ee02db24edfd348d6c4db262","datavalue":{"value":{"entity-type":"item","numeric-id":3583296,"id":"Q3583296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$FB6F53E9-1D22-4321-8216-DAA69B5E9D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39955230987edbd9b04725f49e22d86a615e40b4","datavalue":{"value":{"entity-type":"item","numeric-id":3231818,"id":"Q3231818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$D197BABF-B8DB-4F1B-8D81-C3D1594C7A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0307aeb51722bf49dd97b50bac6d95d4a34ad77","datavalue":{"value":{"entity-type":"item","numeric-id":2425356,"id":"Q2425356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$2999A65A-91F3-45E1-9CFB-4CAB7A2E12AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bb7bbe8743dfedf8c72f40d38e154ca446bfe2","datavalue":{"value":{"entity-type":"item","numeric-id":540028,"id":"Q540028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$F8208723-5D48-450B-B4A0-075D019369BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6268eefd249a61b20a09459e9f5e1550ecff3ca5","datavalue":{"value":{"entity-type":"item","numeric-id":1883683,"id":"Q1883683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$16D09456-069A-4FE6-A80E-0A8ED483B1FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60e805d2a5d9ae2420ea1795506963b669e8e9a6","datavalue":{"value":{"entity-type":"item","numeric-id":874003,"id":"Q874003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$8C3F4925-EA6D-4473-8A76-BD1497D7A65A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2743d51e601f4af68c41a4bde27dde6d983f2e99","datavalue":{"value":{"entity-type":"item","numeric-id":1024499,"id":"Q1024499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396886$964AAF17-20EE-4C79-B583-94F5D95545C9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"65ec9ae6d33c76590a59038aad0cf4b18a8f0bc7","datavalue":{"value":"bafkreiemylrdsemvflqlm6qxozhaf4ixivxuk43kcbufixaorhj3oxn4hm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396886$7E124F71-EDCB-4729-AE9E-4A9003BDB2B9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f089cea9df62e6c2eff010b431437ce87e1a01f2","datavalue":{"value":{"entity-type":"item","numeric-id":2741457,"id":"Q2741457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5637c3686d254d764f5d697c6043ae9f0faacf30","datavalue":{"value":{"amount":"+0.8178199529647827","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":"Q396886$2DFC4BED-FDCB-4E48-9CDE-45D584E6DAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75a5a4202fa8ea3da8b5c89c6de8e73a4e20686","datavalue":{"value":{"entity-type":"item","numeric-id":6046167,"id":"Q6046167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5275b78e5d1b73fd685a225069d653659f3ac67a","datavalue":{"value":{"amount":"+0.8173813223838806","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":"Q396886$4E8413F9-1102-4867-8E52-46D667011F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"918571f2a567ba30502c1f3943fb6aad74871ead","datavalue":{"value":{"entity-type":"item","numeric-id":4279033,"id":"Q4279033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15d1391cfae82e4ec4ce6909aad91e148c39870b","datavalue":{"value":{"amount":"+0.8061962723731995","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":"Q396886$DC2FC940-9A3B-4C58-9A41-FD39D35C48FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce266f995faa62536da77e10e03a350864d7b062","datavalue":{"value":{"entity-type":"item","numeric-id":1025479,"id":"Q1025479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a136336cfb8b428cc9eb9fed7a9efe63cac940d4","datavalue":{"value":{"amount":"+0.803851306438446","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":"Q396886$598E8178-3F0D-43A2-B878-1596EDF78B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0ebb90068aa797e6021f3b751df1ac8ded512c8","datavalue":{"value":{"entity-type":"item","numeric-id":3390050,"id":"Q3390050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cc479fa49f0e6db67eed61165aa52ef15a5a5df","datavalue":{"value":{"amount":"+0.8017780184745789","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":"Q396886$AFC35242-8E29-4773-BE29-0ABA3046D94C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nordhaus-Gaddum theorem for the distinguishing chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nordhaus-Gaddum_theorem_for_the_distinguishing_chromatic_number"}}}}}