{"entities":{"Q2666587":{"pageid":2677330,"ns":120,"title":"Item:Q2666587","lastrevid":57978174,"modified":"2026-04-03T07:52:31Z","type":"item","id":"Q2666587","labels":{"en":{"language":"en","value":"A note on one-sided interval edge colorings of bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7431842"}},"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":"Q2666587$B6EC616E-A889-4B2B-B561-196ECBB16431","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac59d915bab1abc68d5412e75fe93f1a851af621","datavalue":{"value":{"text":"A note on one-sided interval edge colorings of bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2666587$D3F5F290-A124-4203-99F9-53F69F0472FE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52cbde54d026efb7e38b9b9aa4807e5ceb9a2227","datavalue":{"value":"1480.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2666587$81618007-BEED-4334-B03C-32B5E728FFD1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03b0659dc4a395a1284d960142bd1427dea4590c","datavalue":{"value":{"entity-type":"item","numeric-id":292249,"id":"Q292249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$28BD4716-F89C-4DB3-B73B-8BB2776BA3F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$614754EA-F151-473F-9FFA-773A9180433B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f4d88cdf50c95484e0be480b161ba22851940082","datavalue":{"value":{"time":"+2021-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2666587$FA19F2A8-F0E2-426A-8620-5A60DDC0BC40","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4e1e3daeda64881cf587f5339ca20e9198d684d","datavalue":{"value":"https://arxiv.org/abs/2106.13985","type":"string"},"datatype":"url"},"type":"statement","id":"Q2666587$7BA80C8C-1080-4DCB-8E66-5003505462EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcbaa4493ec2fa1fb7a8fef76fad865f80fafc93","datavalue":{"value":"For a proper edge coloring \\(\\varphi\\) of a graph \\(G\\) and \\(v \\in V(G)\\) the palette of \\(v\\), \\(\\varphi(v)\\), is the set of colors appearing on edges incident to \\(v\\). An interval coloring of a graph \\(G\\) is a proper edge coloring by integers such that the palette of \\(v\\) is an interval of integers for any \\(v \\in V(G)\\). For a bipartite graph \\(G=(X,Y; E)\\) with parts \\(X\\) and \\(Y\\) and edge set \\(E=E(G)\\), an \\(X\\)-interval coloring of \\(G\\) is a proper edge coloring such that the palette of \\(v\\) is an interval of integers for any \\(v \\in X\\). The smallest integer \\(t\\) for which there is an \\(X\\)-interval \\(t\\)-coloring of \\(G\\) is denoted by \\(\\chi_{\\textrm{int}}^\\prime(G,X)\\). The invariant is motivated by the problem of finding a timetable where lectures of either teachers or classes are scheduled at consecutive times.  The author proves that there exists a cubic polynomial \\(P(\\Delta)\\) such that for every bipartite graph \\(G=(X,Y;E)\\) with maximum degree \\(\\Delta\\), \\(\\chi_{\\textrm{int}}^\\prime(G,X) \\leq P(\\Delta)\\). This bound is then improved for particular families of bipartite graphs. It is proved that \\(\\chi_{\\textrm{int}}^\\prime(G,X) \\leq 17\\) in any bipartite graph \\(G=(X,Y;E)\\) with \\(\\Delta(G)=6\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2666587$A2138A60-D3F2-47B5-B693-5DBF65634089","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"512183e69be4ab0f9c803f93e55f4d9b77753376","datavalue":{"value":{"entity-type":"item","numeric-id":504963,"id":"Q504963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$A65D832B-8D6A-4028-8FA7-4ED7426E3A76","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2666587$7ED3346B-E837-4A72-8046-7C3712F7CE28","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22077d532073fb7d77428db7996e212d20c63264","datavalue":{"value":"7431842","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2666587$E7F8E7A8-10F4-4398-9A1F-68B8A4C6B973","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0112f4d4011b5712390705f659158fbb5f1cd232","datavalue":{"value":"one-sided interval edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2666587$3442A288-BA4E-47A1-8B23-811E13ED7C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22713fcf0927b69af7b594f12e48b042aa5019b","datavalue":{"value":"interval edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2666587$FBFE98BB-D536-47D3-A8C1-C1C96DA9D058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2666587$31437B60-11A2-42CA-8A6D-DC8A769B4598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2666587$BECD449A-F3C7-4394-97AA-1B856234BED6","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":"Q2666587$FBF009AA-8985-478A-8D53-5C7E54ECAE6F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8d11e47181360dcd20d3b3cd760f6f7906fbafcd","datavalue":{"value":"W3210765568","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2666587$DFAB3750-41E0-400F-BAF9-9CEA38EFBA1D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"77603a316f9fc5a4ef71b23813df472c259d2abf","datavalue":{"value":{"entity-type":"item","numeric-id":4208001,"id":"Q4208001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$B528609A-AA8D-4980-B5A5-056B5F452C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b1d017ac3299079efd4ef60b6355c6a820b9eb6","datavalue":{"value":{"entity-type":"item","numeric-id":882116,"id":"Q882116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$6B8E9CE4-10D2-4B75-B8A4-FB8B461F1007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf3a196d131178fc9f0f6a02fcfdc3974129f98","datavalue":{"value":{"entity-type":"item","numeric-id":4604029,"id":"Q4604029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$53B96523-B79A-4964-847D-6A6B7D3D3921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7b78ccef29cb6d6ddd94b8c79f343448fa0f060","datavalue":{"value":{"entity-type":"item","numeric-id":3632998,"id":"Q3632998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$61DBB58B-8342-4D49-8F1F-712401E0751E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b68ec865cb7baf88f2cd7bcba9c3c7c3fbd782b","datavalue":{"value":{"entity-type":"item","numeric-id":1333322,"id":"Q1333322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$3946B142-FE0C-4C1C-8494-0DDCE3533D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7e52f8b2220c92c060636944ad5cf9ccdcb54db","datavalue":{"value":{"entity-type":"item","numeric-id":4711933,"id":"Q4711933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$C9396280-EDE4-4C06-9ACC-6D883F1C424E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"231951b0ac417f68d1ef0a633a5e1dbe14790ad9","datavalue":{"value":{"entity-type":"item","numeric-id":5217064,"id":"Q5217064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$E0EE4880-5BA8-4540-8E41-071483143AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"050ac9a469249e01447a5e976073451625407a32","datavalue":{"value":{"entity-type":"item","numeric-id":4430881,"id":"Q4430881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$6EDD2BC1-D80C-44F0-B9A9-FBB86ADF6357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8d2ff4268bad63b5ce4cbda0faa0e9cdc4b49e1","datavalue":{"value":{"entity-type":"item","numeric-id":2947944,"id":"Q2947944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$DA6E8877-5F2D-4DE0-9FEE-7C9756A818A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1502747fbcd91e601ab7f11e7aa5eb1172b5d2e3","datavalue":{"value":{"entity-type":"item","numeric-id":2401803,"id":"Q2401803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$8182BD38-A558-4442-848D-2E6CCFA5BC44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0557a17c7d5ac4d5e09450d279b2ca6fe0eb6ab","datavalue":{"value":{"entity-type":"item","numeric-id":2629271,"id":"Q2629271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$1F656519-4426-4539-989A-B95C01818BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07f4c13eae732a653dcba41346fe3812123e6e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5377233,"id":"Q5377233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$DED9355F-BA96-46C6-B830-6DA15A879EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3a31a13cd3aa5bf2a5c6c85126806cf41971a6a","datavalue":{"value":{"entity-type":"item","numeric-id":705502,"id":"Q705502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$B5116F75-8DD9-4778-BC12-D2E2F71881E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6eb15656b0f84ca861bb102eb04603fa36662845","datavalue":{"value":{"entity-type":"item","numeric-id":4393386,"id":"Q4393386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$DCE5BFD5-DBB3-4B29-927B-44221D863886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13adfa7f4185a0eaac26e4928f0665753cb853c","datavalue":{"value":{"entity-type":"item","numeric-id":2713634,"id":"Q2713634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$38CBDCD0-F77E-4825-874E-18CC7239B773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed0c220eb94954ecc2ec5bb2560393a078479712","datavalue":{"value":{"entity-type":"item","numeric-id":2014713,"id":"Q2014713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$02D78BC7-B45C-4D60-AD2C-8E08A9ED42C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$348D3801-F995-4606-B86A-FED5CAE2C71B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfaf4e1dc2a5a43aabe45137ba585ef8ef1cf3","datavalue":{"value":{"entity-type":"item","numeric-id":3456140,"id":"Q3456140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$B422D5A9-1E48-439D-8BEC-7CF7838F2B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcbdf8470cc510a996cb483fa3ada32bff09a911","datavalue":{"value":{"entity-type":"item","numeric-id":3159395,"id":"Q3159395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$09263B40-0FFC-4A18-80BC-DB808DE71D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9474dab375d942e93652994c8c4994e297c0a33","datavalue":{"value":{"entity-type":"item","numeric-id":4033261,"id":"Q4033261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$DF4D6927-6D9C-4F0E-AE49-F183778243D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62f9ac8959a316d9d6224cee5e5b68d63b6eaa5","datavalue":{"value":{"entity-type":"item","numeric-id":3118960,"id":"Q3118960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$A856CDE7-6CA5-4565-ADC1-86A8C4C42D04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4097aa853ae36db70839e7f433d309d147ac79f8","datavalue":{"value":{"entity-type":"item","numeric-id":548414,"id":"Q548414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$6590111A-C2B3-4D96-B182-25BA28B3810D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e743a93d4ff448967e83720a9bc258177bc0789d","datavalue":{"value":"10.1016/J.DISC.2021.112690","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2666587$68FE0B0B-0A32-4BA6-A8F1-9FEEED3558C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a411217c375996dc6183c8687230c5287836c729","datavalue":{"value":{"entity-type":"item","numeric-id":2629271,"id":"Q2629271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41ac3188e4c0467d00d796db37e3f8b19ad89c10","datavalue":{"value":{"amount":"+0.912201762199402","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":"Q2666587$C2313250-8F71-4600-90FD-97C94E62CB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c9bbc6f5f163db298864dd7079c293b5f888c4c","datavalue":{"value":{"entity-type":"item","numeric-id":2947944,"id":"Q2947944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d80e9f283832c480eafd47594f2fb92b50ab3d83","datavalue":{"value":{"amount":"+0.8391668796539307","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":"Q2666587$F334036A-2241-458D-AFD4-19EC75BAD781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a450a7b5cda5ae0ad91c03cae1f69cd161083135","datavalue":{"value":{"entity-type":"item","numeric-id":3456140,"id":"Q3456140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88d1145839644b4c41dfc2e283ed4cc4bb0a1394","datavalue":{"value":{"amount":"+0.826422393321991","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":"Q2666587$FE2B5EAD-8BA2-46D1-B139-CF76635E4848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bea1da10a069bcbed908d124aeeda8c89b7e35a","datavalue":{"value":{"entity-type":"item","numeric-id":5495881,"id":"Q5495881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8247fdeba3974eb49c71e3c8c255ac2090e745e5","datavalue":{"value":{"amount":"+0.8259409070014954","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":"Q2666587$FCB5B13C-80D7-474A-8EB5-FC0931D07BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31d24caefdbf6365caac4dcde97756e99e460a09","datavalue":{"value":{"entity-type":"item","numeric-id":2636801,"id":"Q2636801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b40b30a5ff7e15c00b354054aef54ade7c47780","datavalue":{"value":{"amount":"+0.8249189257621765","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":"Q2666587$10762D8C-7C27-4E4B-A078-879641E2C82E","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2666587$E78FC902-B4E0-4315-A9AA-4650A4F32C3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2666587","badges":[]}}}}}