{"entities":{"Q2439828":{"pageid":2450571,"ns":120,"title":"Item:Q2439828","lastrevid":57927450,"modified":"2026-04-03T03:04:03Z","type":"item","id":"Q2439828","labels":{"en":{"language":"en","value":"Circumference, chromatic number and online coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6270633"}},"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":"Q2439828$B320FF0C-447E-472A-82BA-0316B17BB1B5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d523804fcdf4a047f883614362f96d8924595350","datavalue":{"value":{"text":"Circumference, chromatic number and online coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2439828$E90BF96C-BD8A-4A4E-AB4B-A85A412B98AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c04fe2aceda28d2445a5f05e295b62e812fcef93","datavalue":{"value":"1313.05115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439828$4B2970E0-629C-482D-B386-991B5CC2EB9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"681568a4d55f4dde5b12284e55e95ce150e68da6","datavalue":{"value":{"entity-type":"item","numeric-id":409367,"id":"Q409367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$B5D97B7D-1D6C-4A09-BB90-08870F454360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7a90f13cbd859006e0c22dd1c47d6253d092629","datavalue":{"value":{"entity-type":"item","numeric-id":991783,"id":"Q991783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$E73A2B87-8470-4BB7-97A4-3653A065475A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"256f08c4eec31eb6356087b348ec0eaa953e3474","datavalue":{"value":{"entity-type":"item","numeric-id":879398,"id":"Q879398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$F9BFAE09-6D32-40D2-8E6C-38A44FBB667B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$14B0A495-9F6D-4B6B-81E1-F1BA1C0C8A82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4c390a54d5b8ac5e89f6cda6173ba0d0d0657c1a","datavalue":{"value":{"time":"+2014-03-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2439828$A1555703-041E-4F1C-BC3D-5459AA6A21C7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c35240cb3de17a0b10eb0db571a9bff04c308287","datavalue":{"value":"https://arxiv.org/abs/0809.1710","type":"string"},"datatype":"url"},"type":"statement","id":"Q2439828$9D0A732A-DFB7-4560-B79F-BE8A368FF275","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"897b5599622b9f4371385e2d27b3b469de8c45f6","datavalue":{"value":"Denote in a graph \\(G\\) the length of the longest odd cycle by \\(\\ell(G)\\), and the chromatic number by \\(\\chi(G)\\). The authors address a conjecture of \\textit{P. Erd\u0151s} [Ann. Discrete Math. 51, 69--79 (1992; Zbl 0760.05025)] that a triangle-free graph of chromatic number \\(k\\geq3\\) contains an odd cycle of length at least \\(k^{2-o(1)}\\).   Theorem 7. If \\(G\\) is a triangle-free graph, then \\(\\chi\\leq\\frac{15\\ell}{\\log\\log\\ell}\\).   Theorem 10. If \\(G\\) is a triangle-free graph with no \\(C_5\\) subgraph, then \\(\\chi\\leq6\\sqrt{\\ell}\\).   Theorem 12. If \\(G\\) is a triangle-free graph on \\(n\\) vertices, then \\(\\chi\\leq\\)O\\(\\left(\\sqrt{\\frac{\\ell}{\\log\\ell}}\\cdot\\log n\\right)\\).  Theorem 13. Let \\(k\\) be a positive integer. If a graph \\(G\\) has at most \\(r\\) cycles of different lengths, each \\(1\\bmod k\\), then \\(\\chi(G)\\leq rk+k\\).  Theorem 14. Let \\(k\\) be a non-negative integer. If a graph \\(G\\) has at most \\(s\\) cycles of different lengths \\(2 \\bmod k\\), then \\(\\chi(G)\\leq sk+k+1\\).  Theorem 15. If \\(G\\) is a graph with no cycles of length \\(3 \\bmod k\\), then \\(G\\) is \\(2k\\)-colorable.   From the authors' abstract: ``Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439828$5CB1334F-ED78-4C18-A710-0CC79E6A2E0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439828$72444A67-5118-479C-9324-71EC92EC95BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439828$E44280B3-5E2D-450A-91EB-633FDE9A9F0C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dcabc300f29ff93ab63a6ea97e14afdfd5d8aee2","datavalue":{"value":"6270633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439828$27AFF7D3-C8A6-479C-BBC6-4E577E372810","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439828$263E8111-AA78-42F5-B3C6-63723D791062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"938507bc54d83812726579a12a77d5cd2af4ae8b","datavalue":{"value":"triangle-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439828$180E4F5E-6982-4A10-AD1E-488F7FAF0671","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":"Q2439828$AA2DAC19-80A0-4B20-BA2F-D69C963F8755","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"56d0b4713eab9d349ed1593c47d28259b3953cff","datavalue":{"value":"W2000768672","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439828$7FC8DEB0-AA4D-4922-A88F-1144C109016B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$449711C5-68CE-4398-9395-707DC78D5286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db1b46b9909174603045745034a0c0754236684b","datavalue":{"value":{"entity-type":"item","numeric-id":1301632,"id":"Q1301632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$0155003D-53AE-47EC-93F6-5A55FF10C5D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c4165f8241abf118dcdabeda7e9c3ac51ad0221","datavalue":{"value":{"entity-type":"item","numeric-id":1196747,"id":"Q1196747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$13E78408-5C7F-45E2-A5AC-1482E17FA376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5f29f1fbdbdba8dac7e0f157eac138f8496b1dd","datavalue":{"value":{"entity-type":"item","numeric-id":4763409,"id":"Q4763409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$FF6B7A56-7139-4B17-B5E9-D02137BDF855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c018892c3a60850ad11d9d831b13e9182ea8528","datavalue":{"value":{"entity-type":"item","numeric-id":3437002,"id":"Q3437002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$3722A32A-32B3-4E58-A739-6BBB6CC70E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93986a3e1efa88df7884a3386420df066f13f2df","datavalue":{"value":{"entity-type":"item","numeric-id":1264277,"id":"Q1264277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$6B5928DC-7E00-489B-B22F-B29ACCDAD339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac9c0a0496cac0485cd86316f1d46f4eb449c720","datavalue":{"value":{"entity-type":"item","numeric-id":1124602,"id":"Q1124602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$9CB2F14C-2B5C-4958-8CB1-D031761F86D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e16f51bbd00960cd107d8ad024b1100c25ea1171","datavalue":{"value":{"entity-type":"item","numeric-id":3055917,"id":"Q3055917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$7D8FD4A9-74AA-48FC-AB25-66E60E25F883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2ed1eb294bf113dae778921bdda14bdb7051703","datavalue":{"value":{"entity-type":"item","numeric-id":4250147,"id":"Q4250147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$D0A5D956-FC14-49B8-A3C0-4B6CBAA84361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa92d8cb78816ce1c927f6addc949dff5de3409a","datavalue":{"value":{"entity-type":"item","numeric-id":1883263,"id":"Q1883263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$FFCABBE2-86CF-4593-A84A-DF2F9F5ACCDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98569c781cb0dbf8d89137f80b99301798aa409a","datavalue":{"value":{"entity-type":"item","numeric-id":1969797,"id":"Q1969797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$0247CBF0-7859-458C-AF45-C3D1F888E055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0987492090494e2c6804d657235546e43c891d9","datavalue":{"value":{"entity-type":"item","numeric-id":1601403,"id":"Q1601403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$54964830-CC95-4CC6-BF62-4A2ABCEAF46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad266fb3b1c6c5e3a807915143f36a85b0afeba1","datavalue":{"value":{"entity-type":"item","numeric-id":949802,"id":"Q949802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$8AD4CCE1-FB6D-42FC-80EA-C5E4284D7076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29f9488a111f6593fc6c93e43fccd3042dbabd6c","datavalue":{"value":{"entity-type":"item","numeric-id":921012,"id":"Q921012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439828$D59913C4-38AD-42F0-8FED-52AA4451E014","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"10e5df4c15f024928622bdc4aa998b02a7f8f9d8","datavalue":{"value":"10.1007/S00493-013-2542-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439828$D2CFC961-CF19-4107-9E0B-2EE8565D8D0F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8285b69418a04689ed545130dad98507935fdb6a","datavalue":{"value":{"entity-type":"item","numeric-id":1743172,"id":"Q1743172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17605bd1572e87e571c50f08ce805f5de5df025a","datavalue":{"value":{"amount":"+0.8561628460884094","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":"Q2439828$F9456993-63B2-4DD5-BABB-68258095044B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5427ce8a38aa457c789049293d1e4fd90c9962e9","datavalue":{"value":{"entity-type":"item","numeric-id":974990,"id":"Q974990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e4cc58b3ec73ce47d7a3cb683b12a11ee53545","datavalue":{"value":{"amount":"+0.8158509731292725","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":"Q2439828$524637DC-C326-4C8A-8F62-8BB7D527CB03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d84a3dcc82edba2940aa64951f0becfd2f584c68","datavalue":{"value":{"entity-type":"item","numeric-id":3055917,"id":"Q3055917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fdf46fae721e693775e83a9553d72241d47cb8c","datavalue":{"value":{"amount":"+0.8030691742897034","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":"Q2439828$2A339546-FE76-4159-9F39-602F832F0397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa380f8d71f06d63c6538dd23483b522f584dcdf","datavalue":{"value":{"entity-type":"item","numeric-id":4602857,"id":"Q4602857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11db626fe24dc82b673c2e085dc13e72fff24ae3","datavalue":{"value":{"amount":"+0.8015404939651489","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":"Q2439828$C65830EE-0A6C-45FD-8EEE-921DB72D5CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6ed1b18a6aeae5dec6c2b98a8b6eba2691eefea","datavalue":{"value":{"entity-type":"item","numeric-id":2111913,"id":"Q2111913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e26102e4f6d793ef3e8311fc845c55c17e51408e","datavalue":{"value":{"amount":"+0.7946790456771851","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":"Q2439828$5EC60ECF-D620-418A-AE7F-3EEA79ADE89B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2439828","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2439828"}}}}}