{"entities":{"Q1608645":{"pageid":1619385,"ns":120,"title":"Item:Q1608645","lastrevid":74333583,"modified":"2026-04-14T19:35:41Z","type":"item","id":"Q1608645","labels":{"en":{"language":"en","value":"Uniquely \\(n\\)-colorable and chromatically equivalent graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1777315"}},"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":"Q1608645$78D16589-54AE-4221-B39F-432C5570FF6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a99df21da09afbdbe1334ddbf61c1a028b9e5178","datavalue":{"value":{"text":"Uniquely \\(n\\)-colorable and chromatically equivalent graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1608645$3C1FAC7B-DE93-41C2-875D-6FE68E92A85B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49578fac80ea3bb8a85553a8049a9ae554b79c46","datavalue":{"value":"1008.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1608645$CBA0262A-B772-407D-BE9B-161653BA325F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1cb75dc6f062feb616464ccf45a1b9661d50e1d0","datavalue":{"value":{"entity-type":"item","numeric-id":1053706,"id":"Q1053706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1608645$57103F37-82D2-4A20-A8F3-DBAC4B8E879B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ef1198b0225f4fc027fe11094295f22660c1645a","datavalue":{"value":{"entity-type":"item","numeric-id":223548,"id":"Q223548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1608645$FAA36FF2-1892-4312-BAF9-5C891454ADDB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffa85d9912418bd5ff11b5aa4a0a27f951e2a1ef","datavalue":{"value":{"time":"+2002-08-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1608645$DA3C3967-992A-4FA7-A33C-A44DCC8E072C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"abdf2720b46b8b0889c8951afb4eccc9b7e69968","datavalue":{"value":"https://eudml.org/doc/49854","type":"string"},"datatype":"url"},"type":"statement","id":"Q1608645$3959A0FF-3663-4151-9F3E-9AF87525DFB3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18457f9f8c067a6e2af0b98694c8ede2f3133be7","datavalue":{"value":"A graph is uniquely \\(k\\)-colorable if any proper \\(k\\)-coloring of the vertices induces the very same partition on the vertex set. The main result in the paper is a concrete construction of uniquely \\(n\\)-colorable graph on \\(2n\\) and on \\(2n+1\\) vertices for \\(n>2\\). The key idea is that the complement of a uniquely \\(k\\)-colorable graphs has a unique clique cover of \\(k\\) cliques, so the complement of a path on \\(2n\\) vertices and the complement of a \\((2n+1)\\)-cycle with a short chord suffice. If we substitute each vertex by a clique in the path and cycle examples then we still get complements of uniquely \\(k\\)-colorable graphs, but this case with more vertices. The author also constructs chromatically equivalent but nonisomorphic uniquely \\((n+1)\\)-colorable graphs on \\(2n+2\\) vertices and on \\(2n+3\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$C8C3B384-E68F-4D59-96FE-B8B1F841B1B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d4de3193b89da1a841d76ad5faa949e9be96ad30","datavalue":{"value":{"entity-type":"item","numeric-id":228803,"id":"Q228803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1608645$99CECA2B-FA8C-4EFC-B3FE-DBFC1827149E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1608645$9218D0EB-CA6A-4F8B-9F85-A9CDC1720A11","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5b3301bf7e57012a51c37ba577aca387ba1a87a","datavalue":{"value":"1777315","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1608645$607B5AEC-7E86-4C67-BC82-2DECBDC3CD9C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dbdefa3db098847509217fc561f4908fad8e11c","datavalue":{"value":"uniquely colorable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$C72181B6-C64F-4782-93EE-B70DFCB70045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e237edeea566ee570409decf9ae1ec10587590d","datavalue":{"value":"chromatically equivalent graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$606E2971-D74F-4C71-8D31-5C249DA0B4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50940ff582f152d511fd3e73cca71bead0f1bf00","datavalue":{"value":"chromatic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$2315D915-3DB5-47FF-8870-3EEB336205CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2cd1cb6c1ea8c95dca9eb38f0dfa6e67aa6389f","datavalue":{"value":"complement of a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$6404E0AC-9C5B-4FCA-A7C7-F2AAF230FDD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f2bd7369831d9e54b4e511b9d71ba97d1e383ac","datavalue":{"value":"complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$285D73F5-32E8-4B66-BCB5-4AB6CE37ED26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc2e23ea9a05a5e775747033728c6b9f76e0b733","datavalue":{"value":"clique cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1608645$6764E24A-9BE3-4C68-96D4-3F48625A5BEB","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":"Q1608645$F9A49A5F-8150-4C74-A588-820740AF9A8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b32a70da01ebd5c7ec96470306a7b588028fcc6d","datavalue":{"value":{"entity-type":"item","numeric-id":4327762,"id":"Q4327762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb6e620498236a5ab0dec47cf933013e5ace2eef","datavalue":{"value":{"amount":"+0.9524863","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$EBDB7422-6984-4E37-A042-AF04DE54F7B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b288ca86dd9c3b6b7f467f3514098cdb0aa8f7b1","datavalue":{"value":{"entity-type":"item","numeric-id":1309443,"id":"Q1309443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26b2dc626f8141c2a3b12cad373bc9d1ce16a273","datavalue":{"value":{"amount":"+0.9491825","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$4E1CA638-9A33-4CE3-87B7-A653D0410F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"464a03ba2a3d58ba8e3fb39e251c372918450e73","datavalue":{"value":{"entity-type":"item","numeric-id":5866017,"id":"Q5866017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49beb6571d5806928c1c902ee6dd04214e6b671a","datavalue":{"value":{"amount":"+0.9459758","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$93F355E5-71BC-4B4A-BB9A-E63B6B6FFD1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e26ebb6ca2c73d3c166a7eba6f0bd14d34035c59","datavalue":{"value":{"entity-type":"item","numeric-id":5202203,"id":"Q5202203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c979cefce16381ab7f8927dc86fef161d554dd25","datavalue":{"value":{"amount":"+0.94479287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$136C828B-6C5C-43A2-B540-B8EA98224E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82bce388d6345c978d6d8d364f6abdd44b1913df","datavalue":{"value":{"entity-type":"item","numeric-id":1376076,"id":"Q1376076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cad9a9a114e2f3c339aeec41c28bcaeb2f08b78","datavalue":{"value":{"amount":"+0.9436766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$932EAB3D-C931-45E5-814C-5979A4747352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24e2ec28ba077e49cd14c4b13dd41f944b1841ce","datavalue":{"value":{"entity-type":"item","numeric-id":3699709,"id":"Q3699709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65c4f8ad6a9dbfc6c3524f0ac5bc870b8241017b","datavalue":{"value":{"amount":"+0.93996644","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$AC56241C-A089-40A6-8FF3-6356B24FB2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"975c2412498b87c12453270e468229436ba5814a","datavalue":{"value":{"entity-type":"item","numeric-id":4724656,"id":"Q4724656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2412bb82544543c92a003c17f96baed3f17c6f06","datavalue":{"value":{"amount":"+0.9396321","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$BEECEB2B-4BFE-4F44-9CEC-736DEC62533E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edbf5e71f608977ae30803b3108d14159b6d89c1","datavalue":{"value":{"entity-type":"item","numeric-id":686445,"id":"Q686445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc29a6b9abc3046b14833e79d052e13d5e9c33d1","datavalue":{"value":{"amount":"+0.93738645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$DA0E591F-7CFC-41C6-A0BE-315389077C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe8f2bfa8a2cd86a74597f636516162317cccd78","datavalue":{"value":{"entity-type":"item","numeric-id":4034558,"id":"Q4034558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3f96f21be4f8a58e1dc115913799a882e6a7bc4","datavalue":{"value":{"amount":"+0.9346253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$769908EE-D127-482A-9455-806CD87C739C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52da68a050e22452121956e5ada6bd55b5c890b1","datavalue":{"value":{"entity-type":"item","numeric-id":3824333,"id":"Q3824333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfdf7410b556b87f3893370dbbc8e189ca9a7278","datavalue":{"value":{"amount":"+0.9341527","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1608645$84D9F821-F465-4A68-B5E2-29A6226DDE3C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Uniquely \\(n\\)-colorable and chromatically equivalent graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Uniquely_%5C(n%5C)-colorable_and_chromatically_equivalent_graphs"}}}}}