{"entities":{"Q1293205":{"pageid":1303955,"ns":120,"title":"Item:Q1293205","lastrevid":67283943,"modified":"2026-04-12T16:35:29Z","type":"item","id":"Q1293205","labels":{"en":{"language":"en","value":"Sequential colorings and perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1309394"}},"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":"Q1293205$18C4055C-D572-46A7-B0F6-C6D5EA156CC1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60bb01ea907c68a56e24b57c857589b3824aa8fd","datavalue":{"value":{"text":"Sequential colorings and perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1293205$7DEAB478-EA06-4228-9349-D46441F9EA9A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b135d727799c8e8b1f842c0e237d09af6e9347fd","datavalue":{"value":"0930.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$1D53F5D4-C3FD-4C4D-B9A5-5778D6FC41AC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"994a3a95fe075264c087b1f257ff6e51733f1637","datavalue":{"value":"10.1016/S0166-218X(99)00026-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$AB1BC491-62AF-4CDB-A6C5-7A9436914512","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$1C5341E3-D4F2-43DB-9FCB-FAA1FBADA213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eccd330e58db916925e9726f6d3cc506f17a2da","datavalue":{"value":{"entity-type":"item","numeric-id":442401,"id":"Q442401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$030CE012-BC93-4E86-9421-464243CE409A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$F8605476-2E4D-4C24-8546-16120E8D1B54","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"09a44795720544c6f367ce769f28cc2e9bf7cf0a","datavalue":{"value":{"time":"+2000-02-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1293205$4F316F6C-C684-42AF-AF10-9709D39C250D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd259dfc65316638ddaf05d94f6484dd5ae39ec8","datavalue":{"value":"The sequential-X algorithm is an algorithm for coloring the vertices of graph \\(G\\) which, given an ordering \\(v_1,\\dots, v_n\\), colors the vertices of \\(G\\) greedily using the idea of bichromatic interchange. Clearly, every graph has an ordering such that every execution of the sequential-X algorithm on this ordering provides a chromatic coloring. An ordering of the vertices is called sequential-X perfect if for each induced ordered subgraph the sequential-X perfect algorithm produces an optimal coloring. Furthermore, a vertex \\(v\\) of \\(G\\) is called excellent if it does not lie in an odd hole of \\(G\\) and its neighborhood contains no induced \\(P_4\\), \\(3K_2\\) or \\(P_3+ K_2\\). An ordering \\(v_1,\\dots, v_n\\) of the vertices of graph \\(G\\) is called excellent if \\(v_i\\) is excellent in the subgraph of \\(G\\) induced by \\(v_1,\\dots, v_i\\).   The authors show that the sequential-X algorithm when applied to \\(G\\) with an excellent ordering provides a coloring with \\(\\omega(G)\\) colors. This implies that any excellent ordering is sequential-X perfect. They conclude with a polynomial algorithm which, given a graph \\(G\\), either answers that \\(G\\) has no excellent ordering or gives an \\(\\omega(G)\\)-coloring (even if \\(G\\) has no excellent ordering).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1293205$0DADC110-5619-4F62-9188-A8F8F30F6461","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$CF208324-243C-4BAE-9B6F-F41A94AA93BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$FF0AC340-5009-4D9F-BE5B-B1B1DAA004D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$770513BF-5FBB-4638-A834-548B603DE410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$3A907AD3-337F-481B-B3B5-315F2A07697B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$8B078ED3-CC8A-4FED-B121-2948E46E1EC7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db2e6def5f9cfa57ad1dff3ef3e121981eac3d5c","datavalue":{"value":"1309394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$EA7BD741-9C84-4386-B6EE-B12EAC3CFAA6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1293205$A853E59A-CB08-4E04-99A3-D7B90DCD337A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1293205$55CBD884-0978-4701-9467-5818A4688A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1293205$ED1A67BF-0B40-4339-ADE9-432566B0689A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c5c77c7fb22c29fc9d12f730d8186fbe116e881","datavalue":{"value":"bichromatic interchange","type":"string"},"datatype":"string"},"type":"statement","id":"Q1293205$3A7C1FC6-56FC-4A91-8D99-C0767F5005EB","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":"Q1293205$E91C039A-5066-42C8-8EA1-730181C3102F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09b06ada4a02303c79d7ffc00581d47956a243d6","datavalue":{"value":{"entity-type":"item","numeric-id":4099676,"id":"Q4099676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$CD247894-14F4-404E-8AC8-BBEBEB8D5483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bd269295ba877c106cd58908caf0f087a4411b","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$5241AEE0-5B03-43AA-8AAD-9F3DD8F00A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edc2fe01664e7ae5dbedc60a81011b311142a1b","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$EFCB05EE-6ED0-404E-84B2-8B6F0AE2E0A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$074B563D-6098-453D-88AE-0CBF483FD636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$B4A1EA6F-4315-443A-8DE1-7EF31EF9E25F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$DF969A01-15DB-4038-B99C-701BB967ED9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$5F0D377D-83D0-40FB-A497-035564B67D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b3c99368ea38ef93edcc839b4081d214aa7efc0","datavalue":{"value":{"entity-type":"item","numeric-id":2553372,"id":"Q2553372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$C3EA148A-08C7-49A8-8659-73C23FF96974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b20cf664623a38771ea82582ccdd7db09d37e890","datavalue":{"value":{"entity-type":"item","numeric-id":4894623,"id":"Q4894623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$51D16C9C-F2E7-49AA-AD91-2163D3A9EFC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef4754f01c6e5f4fbaf7f8521f5e41346da3c07f","datavalue":{"value":{"entity-type":"item","numeric-id":2563166,"id":"Q2563166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$D7766D5B-3FC2-400C-8B76-D267DB41E749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d12752e7e3b87a1df82f1629f2c888413b32ca16","datavalue":{"value":{"entity-type":"item","numeric-id":1071025,"id":"Q1071025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1293205$9A5F2F48-2FDC-4CAB-BE66-0C77CBB3F9A1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3da48acec511447482a0b1598f4edaec46ccfb1a","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00026-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1293205$3E74A63E-D5B9-4ED2-A0D4-C625EA826733","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4c5018d2264962dd95b394b9854c1f2005593dd7","datavalue":{"value":"W1982847918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1293205$F51E39A3-8B2A-40BD-8C2B-48B3E1039B27","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c081ea0eed3cd125588696612aa2de6f130ebafb","datavalue":{"value":{"entity-type":"item","numeric-id":4407446,"id":"Q4407446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce1784d7af1a5e1a689a2f240f979804df054e4d","datavalue":{"value":{"amount":"+0.7963042259216309","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":"Q1293205$EBB73EDC-DFE3-4DAC-9791-D759219D463F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f48aaef422cb96624f05377dd9f254214ba8856c","datavalue":{"value":{"entity-type":"item","numeric-id":4854623,"id":"Q4854623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5f2670f2b54aa50dca96944db2ae7de82ee4371","datavalue":{"value":{"amount":"+0.7870845794677734","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":"Q1293205$0B179648-A840-4DFE-8AEA-865EAD1E5640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba2090cca2df7aa19e7f15695b75f58a026fe8e2","datavalue":{"value":{"entity-type":"item","numeric-id":4857449,"id":"Q4857449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11f830d1ec9d811dc941891ef1592fb9767c6bbd","datavalue":{"value":{"amount":"+0.7730259299278259","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":"Q1293205$64CC260A-B802-4DAB-B346-07ADDD3A3D1E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sequential colorings and perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sequential_colorings_and_perfect_graphs"}}}}}