{"entities":{"Q2665834":{"pageid":2676577,"ns":120,"title":"Item:Q2665834","lastrevid":57977820,"modified":"2026-04-03T07:50:28Z","type":"item","id":"Q2665834","labels":{"en":{"language":"en","value":"On properly ordered coloring of vertices in a vertex-weighted graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7430973"}},"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":"Q2665834$6E3E49FD-51DC-4E6A-A7A3-291BFE1F13CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"96200ada658ba733e82c8f064ae13b8a0f4f99a1","datavalue":{"value":{"text":"On properly ordered coloring of vertices in a vertex-weighted graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2665834$9199A8A3-272F-4957-8B0F-2949E23B53DF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42ba8d7922e47feae5ac5bb1bc0a0766d932751c","datavalue":{"value":"1484.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2665834$21CF3A8F-2B2B-4021-A01C-4976F4BBCD37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8be7c510457dea74e91b46714dd152d97da1e670","datavalue":{"value":{"entity-type":"item","numeric-id":323045,"id":"Q323045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$1670A1B0-FC0C-4815-B590-FE27E1A02A36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93d5b529cb72dbee5219c8278759bd209575efcd","datavalue":{"value":{"entity-type":"item","numeric-id":284735,"id":"Q284735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$249980C2-5359-4FA0-805E-1203E2D024BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ef1ff62712ee43ec6fff393675fbfecd5c1f71e","datavalue":{"value":{"entity-type":"item","numeric-id":1227774,"id":"Q1227774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$AB98543D-EFE6-43EA-9BE7-FF5926CDA352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8783284bba8a6466c7dcb01a7d6bcf4759911b8","datavalue":{"value":{"entity-type":"item","numeric-id":186291,"id":"Q186291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$7672443B-D007-42CA-9FC0-A176C4D1A203","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$E595D9E3-424F-4BCA-B9BF-AABF059D5C18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"367677b6c5d204ad2ea10438908eaecdeb1495e8","datavalue":{"value":{"time":"+2021-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2665834$C2DDC1BD-6D18-4C0D-8466-E4C2E2BE7425","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc119b3be9e1c50434bd6cc529562615e6e7cb83","datavalue":{"value":"https://arxiv.org/abs/2102.08432","type":"string"},"datatype":"url"},"type":"statement","id":"Q2665834$7B757FF5-CCD8-481C-8D76-B6CFA01B0058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"bece44f72ecadd9e118f1a8eb88343d1467778f1","datavalue":{"value":"https://strathprints.strath.ac.uk/75253/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2665834$0143BD48-A255-4806-8209-929487B22A72","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cfdb875e507ac7571688180ed6f0ac3eeb6b72db","datavalue":{"value":"In this paper, the authors introduce the notion of \\textit{properly order coloring} of a weighted graph, or \\textit{POC}, which generalizes the notion of vertex coloring of a graph.  Let \\((G,w)\\) be a vertex-weighted graph with vertex set \\(V(G)\\), edge set \\(E(G)\\) and a weight function \\(w: V(G)\\rightarrow W\\), where \\(W\\) is a set of positive integers. A vertex coloring \\(c: V(G)\\rightarrow C\\) on \\((G,w)\\), where \\(C=\\{1,2,\\dots,\\theta\\}\\), is a properly ordered coloring (POC) if for any edge \\(uv\\in E(G)\\) the following conditions hold: \\begin{itemize} \\item if \\(w(u)>w(v)\\), then \\(c(u)>c(v)\\); \\item if \\(w(u)=w(v)\\), then \\(c(u)\\ne c(v)\\). \\end{itemize}  Then the authors define: \\[ \\chi_{POC}(G,w):=\\min\\{\\theta\\mid c\\text{ is a POC on }(G,w)\\} \\] and \\[ f(G):=\\max\\{\\chi_{POC}(G,w)\\mid w \\text{ is a weight function on }G\\}. \\] Then, denoted by \\(l(G)\\) the number of vertices of a longest path in a graph \\(G\\), they prove the following:   Theorem 1. Any graph \\(G\\) satisfies \\(f(G)=l(G)\\).  The authors define also: \\[ \\chi_{POC}(G;t):=\\min\\{p\\mid \\chi_{POC}(G,w)\\le p\\text{ for every }w\\text{ with }|W|=t\\} \\] and prove:  Theorem 2. For a positive integer \\(t\\), any graph \\(G\\) satisfies \\[ \\dfrac{\\chi_{POC}(G;t)-1}{\\chi(G)-1}\\le t. \\]  At last, given a digraph \\(D\\), let \\(l'(D)\\) be the number of vertices of a longest directed path in \\(D\\). The authors call an acyclic orientation for a vertex weighted graph \\((G,w)\\) \\textit{good} if \\(w(x)\\ge w(y)\\) holds for any arc \\((x,y)\\) in the orientation. Then, defined: \\[ l'(G,w):=\\min\\{l'(D)\\mid D\\text{ is a good acyclic orientation on }(G,w) \\] the authors prove the following:  Theorem 3. Any weighted graph \\((G,w)\\) satisfies \\(\\chi_{POC}(G,w)=l'(G,w)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2665834$59585B91-6F92-42F4-BC9A-0CFFA71E16EA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"17425af1eb2cb498b7627d195a6084865f650a48","datavalue":{"value":{"entity-type":"item","numeric-id":763580,"id":"Q763580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$AE095B9A-1C96-4365-8A89-5E68D5F079E4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2665834$4F23685E-21EF-4A54-BE9A-8F4B20401851","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a2b31a57d13dff455cd53d3d30ce89c37202d42e","datavalue":{"value":"7430973","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2665834$0F8664F2-6489-4D14-9771-1E7A903EE371","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2665834$80DA4F8B-F85B-4FE1-8359-E3CF9B05256D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29d71354ba85e09e76f628bf0679b4dddd550ddd","datavalue":{"value":"properly ordered coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2665834$66C11B18-4605-49FD-91AD-E62423C1A7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fd5a3b2d4f213e922e0aed5ce1aa1306f508289","datavalue":{"value":"vertex-weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2665834$C2935A35-8D05-429F-96E2-564D050BEE0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4355927ac0b873d55ff93d0d1839d558db90e1ec","datavalue":{"value":"Gallai-Hasse-Roy-Vitaver theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2665834$61C19D71-E3F4-46D6-B836-C3A5B409934D","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":"Q2665834$8D9D2B89-88B3-4084-8BC1-AAF837E6CC50","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8583a5695b0d1551bf9039d1c94b9a65c41a0979","datavalue":{"value":"W3131303816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2665834$CBC367FC-4D49-4B50-80C8-6E01894614D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdd250a45275500c245c98aa669a4cad3fe76cd","datavalue":{"value":{"entity-type":"item","numeric-id":5545303,"id":"Q5545303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$182521C7-536A-4BEC-9203-9DE3D1924CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21b97a1c274a5f75c018b79e9170da70257e50a","datavalue":{"value":{"entity-type":"item","numeric-id":5617553,"id":"Q5617553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$9905F653-FB3F-4DD5-AAE5-BE23A1740098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fbd86ae02303aa6c9d81c8846e0203674efa6e5","datavalue":{"value":{"entity-type":"item","numeric-id":1022440,"id":"Q1022440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$B964202C-5386-4220-A87D-A0BA7C699AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5acf6ab94da21fc88309f9b2dc3bbfdfe9822b2","datavalue":{"value":{"entity-type":"item","numeric-id":3002686,"id":"Q3002686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$271A5E46-183A-4ED9-A403-E1FFDD4A48FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b64c36f147f07e9132a04121c3023f0fae5bd8","datavalue":{"value":{"entity-type":"item","numeric-id":5539654,"id":"Q5539654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$C3B70586-1F27-4B8C-8B87-5F47B0CE036D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c9d5f997ad4e98faf4457159b52d629b48df3f6","datavalue":{"value":{"entity-type":"item","numeric-id":5331780,"id":"Q5331780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2665834$D662F2CE-55FE-440E-80EA-DD00A06E6EEE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b25e057a3ae4dcfc6e8dc9e77c80e9de0bc52d3b","datavalue":{"value":"10.1007/S11083-021-09554-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2665834$5F8D9212-3BA2-44BD-A5E1-C113C060B36A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f0ec6459519f299a56dc8397e357042775cf477","datavalue":{"value":{"entity-type":"item","numeric-id":3115650,"id":"Q3115650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0817eac34f1deb22f9a9abf3bfa61fb34e45e730","datavalue":{"value":{"amount":"+0.7586038708686829","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":"Q2665834$60DD287B-A4CF-4D52-925B-58468BE1C12C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f817adb5be5cc51da6197c385ffec08ef4016983","datavalue":{"value":{"entity-type":"item","numeric-id":5964985,"id":"Q5964985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7f0b19e89e035125a5627a8956e6cb289a013d9","datavalue":{"value":{"amount":"+0.7544817924499512","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":"Q2665834$3C9EB1A6-806D-4C9A-AC1C-FE2D73C35402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5a34972f85eb311befd06c9166aa59d679e478e","datavalue":{"value":{"entity-type":"item","numeric-id":1896351,"id":"Q1896351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e10c4e4f6a2a23308687af4af137dbc4becbd440","datavalue":{"value":{"amount":"+0.7528508305549622","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":"Q2665834$0969887F-8AE0-4C34-ACE2-A82722241473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4469d27cb4485c3f620c863b1054057d992a36eb","datavalue":{"value":{"entity-type":"item","numeric-id":286971,"id":"Q286971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3ffb482e6e86c6e4ff4817aadb173e956e8c9b4","datavalue":{"value":{"amount":"+0.7495347261428833","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":"Q2665834$FF66702D-145A-43FC-8CA0-F669ECF6BC52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f48aaef422cb96624f05377dd9f254214ba8856c","datavalue":{"value":{"entity-type":"item","numeric-id":4854623,"id":"Q4854623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b15c26a3f0d64e212780c6884ab894ac85ad31cb","datavalue":{"value":{"amount":"+0.7475879192352295","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":"Q2665834$C4F5F45F-5F92-42DC-9FB3-774EF4F4CCAA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2665834","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2665834"}}}}}