{"entities":{"Q551227":{"pageid":552994,"ns":120,"title":"Item:Q551227","lastrevid":62690334,"modified":"2026-04-11T07:47:51Z","type":"item","id":"Q551227","labels":{"en":{"language":"en","value":"On-line Ramsey theory for bounded degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5923992"}},"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":"Q551227$46E8E762-AF9C-406D-B095-32AC9F21BBC7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a7a4f22f1ff349c5ccefa121586673e9a18a2a8c","datavalue":{"value":{"text":"On-line Ramsey theory for bounded degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q551227$05D6E46D-103C-42D1-BC27-50233BD41934","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bc5da2b69e68000869824f38ae2221f14293cb68","datavalue":{"value":"1225.05179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q551227$A953A339-F2DF-4B70-99DB-8AE22CB2914E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca381e5ecbefb1ef27355803e3b170523bd1d723","datavalue":{"value":{"entity-type":"item","numeric-id":551225,"id":"Q551225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q551227$E40ECC23-ED5A-4B8A-BC62-A7C553D55E01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea6c9ec589ad1c29e012f601e7f530bd1d9cb839","datavalue":{"value":{"entity-type":"item","numeric-id":265088,"id":"Q265088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q551227$E4F48381-9240-43BC-996A-2B08F7F2E9AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bda6634bd9b704666aafb27971d31fe0a008c4ad","datavalue":{"value":{"entity-type":"item","numeric-id":405188,"id":"Q405188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q551227$ECDE1A7C-B5A5-4B95-819B-A8DF6A001998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d688d7ec7d1752372dc1b5584460cb2b48f80903","datavalue":{"value":{"entity-type":"item","numeric-id":551226,"id":"Q551226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q551227$BC31FA43-82CC-4E78-9FDD-AA5537183771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q551227$B71FBC58-13C4-4867-BF7C-1059527091C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"21a59837b2301bc3ff51dd8e1ffa173a0ed27d24","datavalue":{"value":{"entity-type":"item","numeric-id":1929214,"id":"Q1929214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q551227$C0F821D0-BDAE-4B48-B308-08CDA1148211","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":"Q551227$F2B2C92B-35E9-45FE-9F92-8CDB8C0FBD93","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9e9c4f01bcbc42081218933cd52861b8a4f99975","datavalue":{"value":{"time":"+2011-07-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q551227$1CBCC6C9-8126-4040-8FC2-BD806E8F6BEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ae83eadf0f2f2aa57ce7ef4165145ecddf442bf2","datavalue":{"value":"https://eudml.org/doc/226131","type":"string"},"datatype":"url"},"type":"statement","id":"Q551227$FB2C683F-430A-4BAB-B995-9D1E488F3285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"3a6070979a8307b11cddabda217dd1e18d23613e","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p136.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q551227$613B8573-9B6E-46F0-8738-63E7F2719B73","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ccde8183efd608f71696158ce7a37eeb203051f0","datavalue":{"value":"Summary: When graph Ramsey theory is viewed as a game, ``Painter'' 2-colors the edges of a graph presented by ``Builder''. Builder wins if every coloring has a monochromatic copy of a fixed graph \\(G\\). In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class \\({\\mathcal H}\\). Builder wins the game \\((G,{\\mathcal H})\\) if a monochromatic copy of \\(G\\) can be forced. The on-line degree Ramsey number \\({\\overset{\\scriptscriptstyle\\circ} R}_\\Delta(G)\\) is the least \\(k\\) such that Builder wins \\((G,{\\mathcal H})\\) when \\({\\mathcal H}\\) is the class of graphs with maximum degree at most \\(k\\). Our results include: {\\parindent=5mm \\begin{itemize}\\item[1)]\\({\\overset{\\scriptscriptstyle\\circ} R}_\\Delta(G)\\leq 3\\) if and only if \\(G\\) is a linear forest or each component lies inside \\(K_{1,3}\\). \\item[2)]\\({\\overset{\\scriptscriptstyle\\circ} R}_\\Delta(G)\\geq\\Delta(G)+ t- 1\\), where \\(t= \\max_{uv\\in E(G)}\\min\\{d(u), d(v)\\}\\). \\item[3)]\\({\\overset{\\scriptscriptstyle\\circ} \\Delta}(G)\\leq d_1+ d_2- 1\\) for a tree \\(G\\), where \\(d_1\\) and \\(d_2\\) are two largest vertex degrees. \\item[4)]\\(4\\leq{\\overset{\\scriptscriptstyle\\circ}\\Delta}(C_n)\\leq 5\\), with \\({\\overset{\\scriptscriptstyle\\circ} R}_\\Delta(C_n)= 4\\) except for finitely many odd values of \\(n\\). \\item[5)]\\({\\overset{\\scriptscriptstyle\\circ} R}_\\Delta(G)\\leq 6\\) when \\(\\Delta(G)\\leq 2\\).  \\end{itemize}} The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays ``consistently''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q551227$92DFB965-11FC-469C-A3E1-0222B2C135BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q551227$CDA849F2-6DB4-45A1-B0DA-A225AD0C9C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q551227$A5DCB71F-F58F-4141-81D7-53EA349F1202","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4313661e6d08afb932cd1cada79188c4fba9eac5","datavalue":{"value":"5923992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q551227$B5D2AC91-5072-4C85-A56D-822663682C34","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":"Q551227$AA58371A-EB08-4C91-8004-CC0D06825BC0","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"cdfb46c49830990e84e13f6f69df4c3e28458f23","datavalue":{"value":"bafkreiffg7x3vyf3gtlb5ppsnll6uk7glrvevxqyzi2b7ap6wh5ogaz2am","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q551227$F774A9FF-8A57-404F-8D62-DE8A00800EC7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9178275c81d5fcad861482efb4401359a40e10da","datavalue":{"value":{"entity-type":"item","numeric-id":390276,"id":"Q390276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e741e355779aa03829778e43315df295f8a48c42","datavalue":{"value":{"amount":"+0.9280694723129272","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":"Q551227$F0EB322B-2A8E-4A2C-9081-BC2A8F04259C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fea117abb8b247f2a5b8209c930d6f68a767f78","datavalue":{"value":{"entity-type":"item","numeric-id":640428,"id":"Q640428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5930ad4f238880108655a36bd46fb1f7240e02ca","datavalue":{"value":{"amount":"+0.9133460521697998","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":"Q551227$C30B3458-BA1B-49CE-97D1-AB2CB52D1015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47ee586d33b92c5c2aeebbded3c14ad9e4acda0d","datavalue":{"value":{"entity-type":"item","numeric-id":3058538,"id":"Q3058538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"030c2cc963ad0a6e7c16ef15febd07fe3a231ed1","datavalue":{"value":{"amount":"+0.8834909796714783","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":"Q551227$BCBEE3F2-C450-4456-8E1C-6878703F14F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74ab0ddc5a5b6279fadfb34e97b241c20bd73e92","datavalue":{"value":{"entity-type":"item","numeric-id":2185753,"id":"Q2185753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cde235b7d91ba7640583a32b837a8299349f58d2","datavalue":{"value":{"amount":"+0.8772335648536682","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":"Q551227$7AFB35B8-4244-4159-B4F2-D464547024BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29fcce3bb68b7548b1f744f017f605f02d5d5fce","datavalue":{"value":{"entity-type":"item","numeric-id":3575431,"id":"Q3575431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca14834bf319f21bfa3e1ebba2fc6c8c16de9a8f","datavalue":{"value":{"amount":"+0.8733900189399719","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":"Q551227$B66655F6-4861-4D26-81B2-7238CD9A6131","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On-line Ramsey theory for bounded degree graphs","badges":[]}}}}}