{"entities":{"Q1763479":{"pageid":1774221,"ns":120,"title":"Item:Q1763479","lastrevid":73855749,"modified":"2026-04-14T17:30:43Z","type":"item","id":"Q1763479","labels":{"en":{"language":"en","value":"Hamiltonian colorings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2136336"}},"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":"Q1763479$3E3ADBF9-1F4E-435D-8077-2929ED48ABC8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6aa0dc4588beebeb77aaf57ee4a524d46b49fbd","datavalue":{"value":{"text":"Hamiltonian colorings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1763479$2E86CF80-3C0B-4ED1-B212-068192738A6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82be52a71620dfae11ce2c65d429125f3e4c0313","datavalue":{"value":"1056.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$9A8B0F87-0584-4D23-AFDB-8F67A8A3ED72","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e9da64877759bbc88a07be9f6dec74cbbc48ac2","datavalue":{"value":{"entity-type":"item","numeric-id":230773,"id":"Q230773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$6493B6D2-4D9E-48F6-A7F5-8474C2A79D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a29140096635a5fff5e0cde1a9941158d1209ff2","datavalue":{"value":{"entity-type":"item","numeric-id":190566,"id":"Q190566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$037718D1-D9BF-4BF5-9D6E-C61F459E112D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"376e7dc3349fa03a8d8dc2066d4968146c29e639","datavalue":{"value":{"entity-type":"item","numeric-id":189953,"id":"Q189953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$50315FD1-9A10-4C42-82AB-8256E6D5125E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$E95B1B40-68FF-49AE-8538-BE78239A96E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6fd9f57da46494686492c936ca92ef875382ca4","datavalue":{"value":{"time":"+2005-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1763479$A55843BB-83BC-4C2A-A9E0-A43FCD1E6587","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc97a5c772571568fc498609184621792dab5410","datavalue":{"value":"A new chromatic parameter of graphs, the Hamiltonian chromatic number, is introduced in this paper. For vertices \\(u\\) and \\(v\\) in a connected graph \\(G\\) of order \\(n\\), the length of a longest \\(u\\)-\\(v\\) path in \\(G\\) is denoted by \\(D(u,v)\\). A Hamiltonian coloring \\(c\\) of \\(G\\) is an assignment \\(c\\) of colors (positive integers) to the vertices of \\(G\\) such that \\(D(u,v)+| c(u)-c(v)| \\geq n-1\\) for every two distinct vertices \\(u\\) and \\(v\\) of \\(G\\). The value \\(\\text{hc}(c)\\) of a Hamiltonian coloring \\(c\\) of \\(G\\) is the maximum color assigned to a vertex of \\(G\\). The Hamiltonian chromatic number \\(\\text{hc}(G)\\) of \\(G\\) is \\(\\min\\{\\text{hc}(c)\\}\\) over all Hamiltonian colorings \\(c\\) of \\(G\\). This parameter is determined for complete graphs \\(K_n\\), the complete bipartite graphs \\(K_{r,s}\\) and for the cycle \\(C_n\\) as follows: \\(\\text{hc}(K_n)=1\\), \\(\\text{hc}(K_{1,n-1})=(n-2)^2+1\\) for \\(n\\geq2\\), \\(\\text{hc}(K_{r,r})=r\\) for \\(r\\geq2\\), \\(\\text{hc}(K_{r,1})= (s-1)^2+(r-1)^2\\) for \\(2\\leq r<s\\), and \\(\\text{hc}(C_n)=n-2\\). The following two general results are proved as well: (1) For every two integers \\(k\\) and \\(n\\) with \\(k\\geq1\\) and \\(n\\geq3\\), there exists a Hamiltonian graph of order \\(n\\) with Hamiltonian chromatic number \\(k\\) if and only if \\(1\\leq k\\leq n-2\\). (2) If \\(G\\) is a nontrivial connected graph of order \\(n\\), then \\(\\text{hc}(G)\\leq(n-2)^2+1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763479$7214F583-E9CB-4207-B72C-A162121654E9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$2116D4C4-F931-43D6-AD2A-C0CA9CE1B6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$A70E33C4-2C38-444E-9BC3-D4012A9EFB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$EC7D3617-4094-4335-8745-BE0F580900B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$3DE9E827-DA71-4984-BF88-E8C63B254928","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"461d8cf851bf8b63efd3abf33d8938e37dbdd3c9","datavalue":{"value":"2136336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$6996526B-A5AF-4ABC-8485-5306AF7F37BC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"850d6af04f13bac8460f7fb11f228549e4728e75","datavalue":{"value":"Hamiltonian coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763479$EE635D25-E9C6-42B6-ABD4-E3A77FC18FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"948c215d107278fffeea8fe55cafe2db0ed7e6dd","datavalue":{"value":"Hamiltonian-connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763479$A9138E3C-CA35-46C8-A6A6-8B959B67FA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a661dba57d6c9d10a375e6f7c69ffae84aeed17e","datavalue":{"value":"Radio coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763479$76996313-4B9D-4A1D-B04C-34AE47B7BF58","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02baa8c7a177bdddffdd29a44a9d552f63adf459","datavalue":{"value":{"entity-type":"item","numeric-id":582576,"id":"Q582576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$F938D11D-FAE0-492F-9A13-46842774241D","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":"Q1763479$FC21ACBB-6F65-4119-89C5-F1405929AAAF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"17df75a6746a3b87dc70416dc7a935797171e0b4","datavalue":{"value":"https://doi.org/10.1016/j.dam.2004.08.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q1763479$2888B439-DFBB-4EB1-ADCA-09C0DF8C5573","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae5be3f066d02a7c1b42eb225a3fcd2e3858b25c","datavalue":{"value":"W2061630761","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$7EE326C5-02D9-43C6-9A2F-C54CF0F2C34C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fbfc4cf83f7c7582c10c00253c5cdb34dc142ab","datavalue":{"value":{"entity-type":"item","numeric-id":2765170,"id":"Q2765170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$413D664D-9F55-485E-9218-258A5DC9E087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa2f065a1412fbf7f16d0b2d576bfd74c26adcdd","datavalue":{"value":{"entity-type":"item","numeric-id":4665539,"id":"Q4665539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$CFBAEAB3-A58C-4026-98A4-5337773F06F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b26383b7958cf905959718d85371f702f184b1","datavalue":{"value":{"entity-type":"item","numeric-id":2718341,"id":"Q2718341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$6805811B-0F80-4008-B977-78E16C450C87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62aaf4d329bec865ac98b12b48be83013d40c04c","datavalue":{"value":{"entity-type":"item","numeric-id":3151349,"id":"Q3151349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$937BB276-DC0B-4EE1-A9FB-C8BAF19DF699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b67b325a175981320a2c02c661d93f4073657cc8","datavalue":{"value":{"entity-type":"item","numeric-id":4823290,"id":"Q4823290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763479$BCA737BF-5D7D-4001-B971-41B4C5809FDE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d91751858d4de3201bca1b534189e6a39f5841e","datavalue":{"value":"10.1016/J.DAM.2004.08.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763479$00D25DFE-2F95-417A-9F7C-F6C9EDB066B5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5059824210be1b0fd1bb3e498019b6ff9f34a538","datavalue":{"value":{"entity-type":"item","numeric-id":1772412,"id":"Q1772412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e9331f62adb638e43f9925c49d5dd0f0a02b144","datavalue":{"value":{"amount":"+0.98901206","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":"Q1763479$90762384-F168-44D6-939F-B03E72CE558A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b54ccbe6b4f625cd9d5e7fd8b012cabb2fe0a051","datavalue":{"value":{"entity-type":"item","numeric-id":1005245,"id":"Q1005245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fd8f4babcf347612f377183e1d6c98f72efe7ff","datavalue":{"value":{"amount":"+0.9774765","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":"Q1763479$B780EE38-5917-42DD-80BA-C59BB90054DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c63aa5f13346e9626c888c7f68689cc467a9bbce","datavalue":{"value":{"entity-type":"item","numeric-id":5419836,"id":"Q5419836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"237e1e8c15bf3fb65e85a1e8440d3ade277ad1d9","datavalue":{"value":{"amount":"+0.9755639","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":"Q1763479$011B7672-9BB8-4901-B05A-78154C8B57CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cd4049eaf7441266210e1a03dc5d563f34e0973","datavalue":{"value":{"entity-type":"item","numeric-id":4677963,"id":"Q4677963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7afe4becc85c364850244e9457427235fad74dc2","datavalue":{"value":{"amount":"+0.9614999","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":"Q1763479$E3980A5E-6B79-4783-B41F-8B41B29139AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8288bd19a541540ae7f7bed7510fb392c7ec4fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4952612,"id":"Q4952612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60722e166df02d5f00349bb77818449cc19bfde4","datavalue":{"value":{"amount":"+0.95847225","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":"Q1763479$374B524D-3C62-478C-9734-20662EC2BE6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46bfa9d84a661a8ce19894bc817b889b0a5487a1","datavalue":{"value":{"entity-type":"item","numeric-id":860408,"id":"Q860408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60722e166df02d5f00349bb77818449cc19bfde4","datavalue":{"value":{"amount":"+0.95847225","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":"Q1763479$221E820C-AAD0-4620-AAF7-56E94F24213C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d59adc918cf38e1838e28068130afb9058e42b4e","datavalue":{"value":{"entity-type":"item","numeric-id":878611,"id":"Q878611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e65250f4b7bf7989767cd94c2ef81a8e0541ca32","datavalue":{"value":{"amount":"+0.9524125","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":"Q1763479$7A1F3483-8203-401E-B2B6-C1ABBAB30303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90e0c26cc8e0d20047da6f8b7dfd3bfb2f1966bd","datavalue":{"value":{"entity-type":"item","numeric-id":3616002,"id":"Q3616002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1a7beeee949ac5b0983f84bc4a82884e51e472e","datavalue":{"value":{"amount":"+0.94968677","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":"Q1763479$07E5EDB8-47F2-4DBD-8F47-1DFDCE691FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51a4c239f536703c0a84cf4574469cc775e79bca","datavalue":{"value":{"entity-type":"item","numeric-id":274671,"id":"Q274671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d71ea85f4ea93e455356b8cfb937972bd21a7361","datavalue":{"value":{"amount":"+0.94054544","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":"Q1763479$AE9866FE-C537-402E-889D-E06BA5B5813B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"439c4ce4d24bcef35ed09a3b062c6e4e0fe26466","datavalue":{"value":{"entity-type":"item","numeric-id":2803806,"id":"Q2803806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0de64654335fac5ab5ea79d47a830a6b6dd7a10","datavalue":{"value":{"amount":"+0.94041735","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":"Q1763479$C066F0A1-F2F4-4AB7-8847-D253E7FEAEF3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hamiltonian colorings of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hamiltonian_colorings_of_graphs"}}}}}