{"entities":{"Q1753125":{"pageid":1763867,"ns":120,"title":"Item:Q1753125","lastrevid":68882673,"modified":"2026-04-13T02:52:19Z","type":"item","id":"Q1753125","labels":{"en":{"language":"en","value":"A new upper bound on the game chromatic index of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873192"}},"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":"Q1753125$CFC77B43-7E30-4C4F-81B8-A69EAF635A88","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dcabdda82943a7e0b98978400acc78ee4bccc2e4","datavalue":{"value":{"text":"A new upper bound on the game chromatic index of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1753125$5EE16BE7-C831-41B8-97B3-5890D47850B7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a58884950c031c5f1272cafe93157cc71c7c586","datavalue":{"value":"1392.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753125$F96516FE-1820-4AB2-8318-BB00D4745D10","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ceffb360cab31379b5028dc3c46bde8162baa4a7","datavalue":{"value":{"entity-type":"item","numeric-id":490260,"id":"Q490260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$93DA86AB-FC05-4C22-B8D5-398E3E4B6304","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":"Q1753125$9BADB98D-1148-4A1A-AF71-28AE1BD1E2A5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1753125$55A86FE2-74A7-49C0-8571-231D8E23D41F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4af56623eb91c85b11937764870ab8655fac746e","datavalue":{"value":"https://arxiv.org/abs/1710.01472","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753125$1CE30412-9E81-4B72-A48D-097CAA2757DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"69179b0bd785a828ae9e503540b500a66407a860","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p33","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753125$CB379A39-B438-4650-A06D-3EB5C0C626DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e16257d0690b57778b37ea1b85948572f745c4d8","datavalue":{"value":"Summary: We study the two-player game where Maker and Breaker alternately color the edges of a given graph \\(G\\) with \\(k\\) colors such that adjacent edges never get the same color. Maker's goal is to play such that at the end of the game, all edges are colored. Vice-versa, Breaker wins as soon as there is an uncolored edge where every color is blocked. The game chromatic index \\(\\chi'_g(G)\\) denotes the smallest \\(k\\) for which Maker has a winning strategy.  The trivial bounds \\(\\Delta(G) \\leq \\chi_g'(G) \\leq 2\\Delta(G)-1\\) hold for every graph \\(G\\), where \\(\\Delta(G)\\) is the maximum degree of \\(G\\). \\textit{A. Beveridge} et al. [Theor. Comput. Sci. 407, No. 1--3, 242--249 (2008; Zbl 1151.91029)] conjectured that there exists a constant \\(c>0\\) such that for any graph \\(G\\) it holds \\(\\chi'_g(G) \\leq (2-c)\\Delta(G)\\), and verified the statement for all \\(\\delta>0\\) and all graphs with \\(\\Delta(G) \\geq (\\frac12+\\delta)|V(G)|\\). In this paper, we show that \\(\\chi'_g(G) \\leq (2-c)\\Delta(G)\\) is true for all graphs \\(G\\) with \\(\\Delta(G) \\geq C \\log |V(G)|\\). In addition, we consider a biased version of the game where Breaker is allowed to color \\(b\\) edges per turn and give bounds on the number of colors needed for Maker to win this biased game.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753125$26067B60-20CC-405E-B0D1-7F12C88603C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753125$ADEB663F-255C-4E27-AF19-364153C044AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753125$CB1BFF55-F295-414C-80AD-570256910280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753125$6AA0D454-0F82-4708-A8CE-8A982A6CDA35","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"429b3ecccfaa00bc7c89f5928457fe8eca14812b","datavalue":{"value":"6873192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753125$F72B2994-76D5-4B29-A018-7DBA81FEAB98","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8d9b90d8cba59aaef1d765ae8eaeda7c123576d","datavalue":{"value":"games on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753125$0495BE3E-7BB1-49F1-A5EC-5498BB45F39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc047062ce587cbbd4cabea844b30d6137383d1a","datavalue":{"value":"edge colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753125$105CB00B-7AB6-4131-9875-DB7769E4C6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb46e33a33c1b77d1ed2cc767c3f60af08afeb5a","datavalue":{"value":"game chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753125$4BB67424-8E8A-4DD4-9F0F-FE2005DE4DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a3114b8e38af5795fb8f5ba430157fd45434e57","datavalue":{"value":"random strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753125$BCB0BA30-61C4-4468-B72B-6902E8BBCACF","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":"Q1753125$6A41F170-CEE6-4A39-A14B-320D5317B3A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eded2c4398d82dd268c8f441cb76c2b116ab2788","datavalue":{"value":{"entity-type":"item","numeric-id":2492207,"id":"Q2492207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$1D1C9567-77F7-4642-B00F-68A811A0E223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f3a9a875a99beefeec394d5bdc28f2b4adc593b","datavalue":{"value":{"entity-type":"item","numeric-id":643001,"id":"Q643001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$1329CE61-4B6D-4D80-BA1E-AA3E66D31BF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6765fece60b2602d436f3654f262b4d7d677849d","datavalue":{"value":{"entity-type":"item","numeric-id":937247,"id":"Q937247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$D4AB6E5B-488D-4BEB-BA7E-8075AF15BD1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de3fbc8121834e5e2d0c8d98de8be43c39cb9c68","datavalue":{"value":{"entity-type":"item","numeric-id":5448049,"id":"Q5448049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$D0668954-7625-489F-B40E-F381C4166FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5b83122b67f2e1c66f3a69975751cdb7ea28dc5","datavalue":{"value":{"entity-type":"item","numeric-id":954995,"id":"Q954995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$59BA4298-EF67-4187-A06B-FBEC364D0F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bdf6794fca485de5d4b036ac57955fe8079ed7d","datavalue":{"value":{"entity-type":"item","numeric-id":5454360,"id":"Q5454360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$0C5C0DFE-9F41-41F7-8B8F-FDB7F75C9306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be26f7e272159179fb92a82bf325bbc7591792f","datavalue":{"value":{"entity-type":"item","numeric-id":2712591,"id":"Q2712591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$9E1FE1EE-6D91-490C-B587-0F053903352B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff4677d1e0ff5f3afddc0e2681e9b159386e0574","datavalue":{"value":{"entity-type":"item","numeric-id":4152069,"id":"Q4152069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$D4C5352C-8DC1-4F6E-8A85-A7E9CE46BA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd229b748885d93a9e51593bfbdc3c6737ab95c2","datavalue":{"value":{"entity-type":"item","numeric-id":1884997,"id":"Q1884997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$93561D7D-C39A-431E-BC9A-8A88FAD2FC58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694ee32736d8cf72f7a59d5ca258e6998a092fe2","datavalue":{"value":{"entity-type":"item","numeric-id":4201568,"id":"Q4201568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$6A820C93-E0AB-485A-A083-99D650E1C851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad529d6ec0e675f838a177305c691d6c788adff","datavalue":{"value":{"entity-type":"item","numeric-id":2848537,"id":"Q2848537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$51D8C398-635E-4EBD-B46B-40E082604894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe95ab492f6938550926513d13b9633fd46444ac","datavalue":{"value":{"entity-type":"item","numeric-id":1095050,"id":"Q1095050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$38701376-6946-4F86-8D0D-D67F8B6E03B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0d028eb290af9b5d292e6c09c4be74c3995de4f","datavalue":{"value":{"entity-type":"item","numeric-id":490261,"id":"Q490261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$D468D30F-FEE5-4B93-AF1D-C85B57C13658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb7340c7e4bad066830d41cd30e631c015cc0e46","datavalue":{"value":{"entity-type":"item","numeric-id":4309985,"id":"Q4309985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$2300B0EC-1C41-4C6D-94C3-1E883EF1C743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fac9003198d177b00eeea0372ad938d136db447","datavalue":{"value":{"entity-type":"item","numeric-id":1331937,"id":"Q1331937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$241445C2-D90C-4418-AC13-4732C9EBE5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d9134334b3799f11cac5c5b734a7df67539d640","datavalue":{"value":{"entity-type":"item","numeric-id":2464148,"id":"Q2464148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753125$933257FA-2B33-470A-B844-06000E1914C5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5b084a302cfc4f9a6e03d000df4414f4134f133b","datavalue":{"value":"bafkreie5jwpqu5mns7abr27uqrc3epg3x4t54p5n2xddwvsejc5tmya5ku","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753125$02A2B2BD-2A0E-414F-971F-057CE0C32F6E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea704fa13320d2f1bbc6c17dc3befd4b16301cc7","datavalue":{"value":{"entity-type":"item","numeric-id":954995,"id":"Q954995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32de621b9ea56ee929b37f54a1d5fc24ce92910e","datavalue":{"value":{"amount":"+0.8351144790649414","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":"Q1753125$82A68BF0-D504-49CF-B736-44CF92E04918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43a793dac5400e3747935d9135b40f321228cfb5","datavalue":{"value":{"entity-type":"item","numeric-id":937247,"id":"Q937247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca74eb4ade007f806d4bdab85efc8e7ffdcc8366","datavalue":{"value":{"amount":"+0.8341200351715088","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":"Q1753125$0972C267-CCA7-4ECA-AD32-AAD9E5991A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2068603269898034860b91c9a3abad9d8c166030","datavalue":{"value":{"entity-type":"item","numeric-id":1884997,"id":"Q1884997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c2429871f2a7bb338e10b81e6fac3f01dcc8918","datavalue":{"value":{"amount":"+0.8306025266647339","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":"Q1753125$1C04A124-7B6D-485B-9726-AE88F141A89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c043728d09df1b9285899c5188c65e875e98b51","datavalue":{"value":{"entity-type":"item","numeric-id":2449078,"id":"Q2449078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dc8a4bf229f6982b6bbd2fc91a62e3508e0a02b","datavalue":{"value":{"amount":"+0.8276126384735107","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":"Q1753125$2090D9E2-1AE6-4A45-B3CD-B059909CC8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82c4fbf3e29dc1470cf85aff754448706f434b7d","datavalue":{"value":{"entity-type":"item","numeric-id":2712591,"id":"Q2712591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f31751720ae6bf9aba8b7490dcd48db3292c2768","datavalue":{"value":{"amount":"+0.8221257925033569","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":"Q1753125$BECE911E-5A6D-48E9-82E7-74CC92D23B89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A new upper bound on the game chromatic index of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_new_upper_bound_on_the_game_chromatic_index_of_graphs"}}}}}