{"entities":{"Q1924134":{"pageid":1934876,"ns":120,"title":"Item:Q1924134","lastrevid":46399575,"modified":"2025-12-24T17:15:41Z","type":"item","id":"Q1924134","labels":{"en":{"language":"en","value":"\\(\\beta\\)-perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 934801"}},"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":"Q1924134$E4621AF8-E156-4DC6-ACD1-C6440658E99B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10ce7506d0d24b694e939372e790a741da4a37db","datavalue":{"value":{"text":"\\(\\beta\\)-perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1924134$31FEB205-9894-4C7C-B497-5CF037B53730","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"186edcd061284ef5e1ec00e6589b03017f7c3753","datavalue":{"value":"0857.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924134$06A51B6C-4D58-4A4E-BE43-5633854960D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924134$48049255-DB47-4E57-AC9C-5687361C26E0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924134$83E45A8E-B913-43AB-9088-E9AB6BB0881C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87c3e3b2ec497a54777723f516b57d715fefe115","datavalue":{"value":{"time":"+1996-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1924134$F092F54A-6D1C-4A6E-9F95-3095A3DBE53C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"579d84df88e3c709163dba3b03ec9038618dd407","datavalue":{"value":"Let \\(\\delta(G)\\) and \\(\\chi(G)\\) denote the minimum degree and chromatic number of the simple graph \\(G\\) respectively. Define \\(\\beta(G)=1+\\max\\{\\delta(H)\\}\\) where \\(H\\) varies over all the induced subgraphs of \\(G\\). It is clear that \\(\\beta(G)\\leq \\chi(G)\\) and \\(G\\) is said to be \\(\\beta\\)-perfect if \\(\\beta(H)= \\chi(H)\\) for each induced subgraph \\(H\\) of \\(G\\). A number of analogs are drawn between \\(\\beta\\)-perfect and perfect graphs and some special classes of \\(\\beta\\)-perfect graphs are introduced. Finally, the authors show that the greedy algorithm can be used to color a graph \\(G\\) with no even cycles using at most \\(2(\\chi(G)-1)\\) colors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924134$54231E7A-A0E3-4341-A35B-89B712DB90DB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a55663aec12fd5dc29d6a06eb35cad7c86131b6","datavalue":{"value":{"entity-type":"item","numeric-id":594869,"id":"Q594869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924134$46962329-F540-4B6B-B01A-3242C313D555","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924134$37A4FA3C-C0D0-4A95-9604-3CFDBACC3556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924134$595AE5F7-1BB2-4560-9A03-6166A3343FF7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a9192cac0e7dc4d0fac772931811a75db9d462e0","datavalue":{"value":"934801","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924134$41E50105-5C40-4BFE-B1DE-52C26204A103","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924134$792B895D-3066-406F-9852-BFC64F06CEA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924134$AFA4FC27-A62E-4768-ACFC-F3CBC98E6DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924134$506545F2-3962-4A4F-B0D8-29FCB6CB84A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924134$5D9EB4DC-DC1C-48B2-AB5D-2E37BFA25F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea6c2a454c967499acc6d5e80ba39aa769fd1e53","datavalue":{"value":"color","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924134$92313C7F-8312-4948-AB9E-EDE506EBDBDE","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":"Q1924134$D0B30E82-820B-4A37-BD74-79B3185DEE65","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"586f3637aac8ebfcfc257cc752829e0f26baf4e0","datavalue":{"value":"https://doi.org/10.1006/jctb.1996.0030","type":"string"},"datatype":"url"},"type":"statement","id":"Q1924134$4ABB1FCF-4512-491F-BAFE-857B33DBD2FA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f16b6ce41b1f8b763cba6349a780403a265f33ff","datavalue":{"value":"W2036522563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924134$8107DF22-511F-491B-8C09-6E1E3946DEAB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"de09c7d1189852925db8999ea2472172aded5fb7","datavalue":{"value":"10.1006/JCTB.1996.0030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924134$CDD2564E-1685-4D2B-99B1-6E0936B23762","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b800afb308dbcb69372886399d09d0280d7d050","datavalue":{"value":{"entity-type":"item","numeric-id":4786793,"id":"Q4786793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b09b267fef86f268059d2704baed688effde49cc","datavalue":{"value":{"amount":"+0.903075397014618","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":"Q1924134$52C2E334-30A6-441F-A95E-1C5292BD750B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e5a44a252527a8e976b2ab6010bf8c8a85fe2a5","datavalue":{"value":{"entity-type":"item","numeric-id":1567275,"id":"Q1567275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"760e70d15caad6066b293feb49495b096e8430e4","datavalue":{"value":{"amount":"+0.877987802028656","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":"Q1924134$95B41460-FCD8-4EF3-B452-E8276D3B5F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6698f11451b7b760b56a169536f435c42b9c494e","datavalue":{"value":{"entity-type":"item","numeric-id":2032702,"id":"Q2032702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0829a6ce86197207aee2248f0f3f2f0393a74f91","datavalue":{"value":{"amount":"+0.817113995552063","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":"Q1924134$7B2C59E3-D18E-4254-9C27-A4CC2D2DA3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9644c3fcfdd21d1c699aa2cbd8a13c26d5b42442","datavalue":{"value":{"entity-type":"item","numeric-id":1928629,"id":"Q1928629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a27140dea696f95dfba0696205a818fa8a47f941","datavalue":{"value":{"amount":"+0.7930949330329895","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":"Q1924134$3177C6D0-1FB8-487F-A2DE-3813DF5C7FC4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1924134","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1924134"}}}}}