{"entities":{"Q1594601":{"pageid":1605341,"ns":120,"title":"Item:Q1594601","lastrevid":47568913,"modified":"2026-01-02T02:39:27Z","type":"item","id":"Q1594601","labels":{"en":{"language":"en","value":"On edge colorings with at least \\(q\\) colors in every subset of \\(p\\) vertices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1560716"}},"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":"Q1594601$59385C34-C262-49F0-8BC0-D109CADAC33D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de225582f19058be1eb3e5215934d41208d45e33","datavalue":{"value":{"text":"On edge colorings with at least \\(q\\) colors in every subset of \\(p\\) vertices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1594601$3397A131-1351-4CE3-934E-3BACE5BC764E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12ca286f9f815a92ddad60570a54e71a567131ee","datavalue":{"value":"0960.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594601$F30BA1FB-2D0A-4532-A1FD-E634BD69645A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2f3fdbf9f8c798d03777e6ed3c1ca10e41eb29d","datavalue":{"value":{"entity-type":"item","numeric-id":190556,"id":"Q190556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1594601$0ABC070D-8C85-42EF-9080-6F2628ACA770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c803686bf2fcaba4242cd6f3926ce0ef99fc6b5","datavalue":{"value":{"entity-type":"item","numeric-id":641169,"id":"Q641169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1594601$55C79911-D7A4-4393-929F-9AC62FBA9259","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":"Q1594601$CD2FF03A-5597-4EC0-8C49-8E9F0BDC346B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1f254fdbb9fe00827c6b84e770ead83cb29ab1e5","datavalue":{"value":{"time":"+2001-02-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":"Q1594601$4E7932F9-CA70-4B6E-9203-EFE17CF983D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c937a6e8fd3550b0cdcb77d063f370f48662f3c9","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r9.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1594601$37C0E897-B152-4A80-A0FF-06CBC70A0AD1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"947e20552d73c35f5a0563ec25604fb6c37af9eb","datavalue":{"value":"For fixed integers \\(p\\) and \\(q\\), an edge coloring of \\(K_{n}\\) is called a \\((p,q)\\)-coloring if the edges of \\(K_{n}\\) in every subset of \\(p\\) vertices are colored with at least \\(q\\) distinct colors. Let \\(f(n,p,q)\\) be the smallest number of colors needed for a \\((p,q)\\)-coloring of \\(K_{n}\\). \\textit{P. Erd\u0151s} and \\textit{A. Gy\u00e1rf\u00e1s} [Combinatorica 17, No. 4, 459-467 (1997; Zbl 0910.05034)] studied this function if \\(p\\) and \\(q\\) are fixed and \\(n\\) tends to infinity. They determined for every \\(p\\) the smallest \\(q\\) \\((=p(p-1)/2-p+3)\\) for which \\(f(n,p,q)\\) is linear in \\(n\\) and the smallest \\(q\\) for which \\(f(n,p,q)\\) is quadratic in \\(n\\). They raised the question whether this is the only \\(q\\) value which results in a linear \\(f(n,p,q)\\). In this paper the behavior of \\(f(n,p,q)\\) between the linear and the quadratic order of magnitude is studied. In particular it is shown that we can have at most \\(\\log p\\) values of \\(q\\) which give a linear \\(f(n,p,q)\\), where \\(\\log p\\) denotes the base 2 logarithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594601$394AAA00-E4E9-4A49-8526-1373985348E8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1594601$7583A668-B74C-49DD-A8A7-448509455A99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594601$035E8A3D-4F13-4362-AAF5-010E5CCE1525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594601$C615B413-85B3-45C3-B6AB-D51378CED27F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86c2bde86ee62ebc69344e028ab1fac274c16020","datavalue":{"value":"1560716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594601$C485DCA9-142D-4C20-96C2-8F92EC5A65F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594601$16E58A4A-D947-4FA8-8D25-C0E78BB446D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6fd08004786c55626377dbd1f4e922d8494d7201","datavalue":{"value":"monochromatic matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594601$53BCF513-750F-4347-9F1A-A2C394AF8DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97dffa5064f3340b5dc1419cb41ee90015f90d71","datavalue":{"value":"probabilistic upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594601$E7014103-36C4-4906-8D02-9B58C7E48244","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":"Q1594601$562D0156-1740-413A-A17D-E3FAAC8300BD","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b301b5253fc58f19516daa4a2192f7658ad84b54","datavalue":{"value":"bafkreicoq3v5cycnd35zr4sq6bm7debjs3dhvvjvfaxkplsy23k4uhjsii","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594601$5CB309F3-498F-42D0-837B-3CC257B6CA7E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2f4093581807535cc26003ac7e9332c6302f458","datavalue":{"value":{"entity-type":"item","numeric-id":2940075,"id":"Q2940075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a8d7c5d34ca41baf1207d6db75b2db38e47e4d7","datavalue":{"value":{"amount":"+0.8787823915481567","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":"Q1594601$19E22E50-E0EE-4DF9-839B-5A4550B23FD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c31edb03b900faeaf8a10a71b2ef13da67e3ee82","datavalue":{"value":{"entity-type":"item","numeric-id":2327227,"id":"Q2327227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"173862251e61665464329e06fb5829b68ae5b87a","datavalue":{"value":{"amount":"+0.8589900732040405","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":"Q1594601$6B8BD714-1434-4809-8DE3-A4DECA480F07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78f796994f48b9e4238806e9f53ce939d4b1e67e","datavalue":{"value":{"entity-type":"item","numeric-id":1280308,"id":"Q1280308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7ad7fb913199f5a32cb5ebca2e8df9f031b5640","datavalue":{"value":{"amount":"+0.8588099479675293","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":"Q1594601$C9BF91AC-D14D-471E-B41A-8BEA4B9CC320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ee6b317b772fbd3ea862363427d58bb9ba805e4","datavalue":{"value":{"entity-type":"item","numeric-id":5466073,"id":"Q5466073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58d8d32819ad1b062fb4aec24f468983660521df","datavalue":{"value":{"amount":"+0.8588096499443054","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":"Q1594601$D409C181-1CE2-422A-BA7D-9C2555886717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a0b251f8a00582a351bce854af23fa913a96b82","datavalue":{"value":{"entity-type":"item","numeric-id":1280270,"id":"Q1280270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51e7e3309dbdc783110476bc9b4c5891b8509e67","datavalue":{"value":{"amount":"+0.8455395698547363","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":"Q1594601$5B0D6B7A-9A9A-4490-AF91-9BA0FE95CF0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1594601","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1594601"}}}}}