{"entities":{"Q2243141":{"pageid":2253884,"ns":120,"title":"Item:Q2243141","lastrevid":57803898,"modified":"2026-04-02T14:41:59Z","type":"item","id":"Q2243141","labels":{"en":{"language":"en","value":"New bounds for the \\(b\\)-chromatic number of vertex deleted graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7423985"}},"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":"Q2243141$77FEB3D5-8298-4881-90EE-FA830018A86C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34dab0f5e882ed0c256b7c6fc3e1a1c63d28b88d","datavalue":{"value":{"text":"New bounds for the \\(b\\)-chromatic number of vertex deleted graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2243141$5572AA21-F2C1-4420-9BA5-E7AD4F395E62","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c250c68a470365d49fd8ce10fa49149863e5848","datavalue":{"value":"1483.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243141$60C2F717-154C-4327-8DC3-23FFD12B5403","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd389de41ec2e0a5d594b468aceb1c71dbfc801e","datavalue":{"value":{"entity-type":"item","numeric-id":324715,"id":"Q324715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$8FCD666C-9C80-4544-9781-AEA9F827AB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da78aa215e53116ae7cdc92be40391868a73c971","datavalue":{"value":{"entity-type":"item","numeric-id":168584,"id":"Q168584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$FDA1822F-9713-44CD-A89B-337E1270D3BF","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":"Q2243141$76C96123-E006-410A-93C4-B9883A8831D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ff0991cde18ec724825a8f6357cb1656c5a612de","datavalue":{"value":{"time":"+2021-11-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2243141$A46D8808-1AF2-46F8-AA8D-508C5945BC3B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d218bcd5b08041a3d5c7d878741582b4958b7faf","datavalue":{"value":"https://arxiv.org/abs/1904.01600","type":"string"},"datatype":"url"},"type":"statement","id":"Q2243141$019ECED4-9C81-4549-B38E-0A1CEBF89A75","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa5bd2d25d7e75762aba82d4715651bd0adc639e","datavalue":{"value":"A \\(b\\)-coloring is a proper vertex coloring of a graph such that each color class contains a vertex that has a neighbor in all other color classes. The \\(b\\)-chromatic number of a graph \\(G\\) is the largest integer \\(\\chi_b(G)\\) for which \\(G\\) admits a \\(b\\)-coloring with \\(\\chi_b(G)\\) colors.  For a vertex \\(v\\) of a graph \\(G\\), the vertex-deleted subgraph of \\(G\\) is obtained by deleting \\(v\\) and all edges incident to \\(v\\). It is known that the difference between the \\(b\\)-chromatic number of a graph and the \\(b\\)-chromatic number of its vertex-deleted subgraph can be arbitrarily large.  The main goal of this note is to establish lower bounds on the \\(b\\)-chromatic number of a vertex-deleted subgraph of \\(G\\), where \\(G\\) belongs to a class of claw-free graphs or chordal graphs. In particular, it is shown that the \\(b\\)-chromatic number of a vertex-deleted subgraph of \\(G\\) can have a maximum variation of two colors compared to the \\(b\\)-chromatic number of \\(G\\) if \\(G\\) is a claw-free graph, while this difference is at most one if \\(G\\) is a chordal graph.  The paper concludes with a result, which shows that the difference between the \\(b\\)-chromatic number of a graph with girth of at least five and the \\(b\\)-chromatic number of its vertex-deleted subgraph cannot be bigger than two.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243141$337C3FA7-45E8-427E-9CA5-2E8E83B10E61","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"091ba179324c515c5e5d748b86d31c9f0c1910f8","datavalue":{"value":{"entity-type":"item","numeric-id":233536,"id":"Q233536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$4E5EC25A-EA4B-48A0-84DE-EA7A581367C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243141$075F5A37-5A07-41B2-A9EB-08A3DD4F5F2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0a357c1403d2c5f50484e9808f904e0975ea84db","datavalue":{"value":"7423985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243141$FD5707F4-099A-4B18-B4FC-E6B3F137B799","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40e71a9607d37a846c43dfabdc51ac75d0ebbc48","datavalue":{"value":"\\(b\\)-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243141$852F45B6-F314-47AE-B874-344EA9C2E8E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243141$D4F13E94-4412-40D9-846C-A88796A90426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf2bdc388a8c2bee548ba5c2acc5f66c693118c4","datavalue":{"value":"claw-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243141$4E576071-97B7-412B-A75E-A07A38D437F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243141$936442B7-1897-42FB-9818-9A59610CD6C5","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":"Q2243141$A50A6B1B-20B3-497C-82B8-9493F2FC3067","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a3fcd156b24f822c65e9980fe6a57c0af9c93086","datavalue":{"value":"W3205381827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243141$E83C9D51-2ED0-4A10-9A70-0D77702067F4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d49e24f06e9597590b33f54491c649035fbc2b32","datavalue":{"value":{"entity-type":"item","numeric-id":2851488,"id":"Q2851488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$1FDD9FEB-52A4-42CB-BE48-E7604BBC9667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0e86be91587c870f37351ab6d3fa839d55995e8","datavalue":{"value":{"entity-type":"item","numeric-id":1043801,"id":"Q1043801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$38E864B8-B1BE-4421-B88F-70C78AAB7C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e06bc0b55fa08ea2b25d86136ab05cd26e4fe487","datavalue":{"value":{"entity-type":"item","numeric-id":2352073,"id":"Q2352073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$0FE26571-6BCE-4085-BE2B-44665F0FEDBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da69c85b3fe3c89a706a8e57115928ae1fd566ef","datavalue":{"value":{"entity-type":"item","numeric-id":2346588,"id":"Q2346588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$FF9B9139-4FD4-4AB5-A3C2-0E0A314C8B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64030798c5b30ddb45b9b56fed9a1b5cc8a892b2","datavalue":{"value":{"entity-type":"item","numeric-id":2576347,"id":"Q2576347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$0D20D539-5E4D-402B-B65F-5E31B7E245FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8061f104280088a601db366286deefe82ac73c86","datavalue":{"value":{"entity-type":"item","numeric-id":1283791,"id":"Q1283791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$98B53FFC-5ECD-4A51-954F-3F115D49A812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78c43fc15a9b158857075d137e8173dfffddf38f","datavalue":{"value":{"entity-type":"item","numeric-id":1682893,"id":"Q1682893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$B8141C82-70F2-4ECA-B5BA-69A20ABE16A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c8f3b5dabee2b380c113032cd7ae1395e7d196a","datavalue":{"value":{"entity-type":"item","numeric-id":897599,"id":"Q897599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$D27C6074-6C0B-406C-AA44-4D405A279FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e7c64af77ae2dea2fe803c2e99ada56d87f7a83","datavalue":{"value":{"entity-type":"item","numeric-id":2488938,"id":"Q2488938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243141$6340A4D3-6CFA-4357-B5E7-2B0D556AE8D9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e6e4933fde62f83f647db6c6df082f9e2a1fdbc","datavalue":{"value":"10.1016/J.DAM.2021.09.023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243141$DB1D2EED-039A-4BFE-AFBC-6CE500CC6E7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0097b43713c10f5b1fe67d99baf0fe24e84a3e10","datavalue":{"value":{"entity-type":"item","numeric-id":339486,"id":"Q339486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbb300d03eec768ebafb232c246fe61c320940a4","datavalue":{"value":{"amount":"+0.8859095573425293","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":"Q2243141$21C963D2-0A1E-4EC6-B38A-E9E7A2AC539D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3ed6fe46528f9387049dc44370b6984ab47028c","datavalue":{"value":{"entity-type":"item","numeric-id":385136,"id":"Q385136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f377450eb38cabe2f572f9dd6766db84671c4b72","datavalue":{"value":{"amount":"+0.8793057203292847","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":"Q2243141$A47CC1B2-604D-4BD0-8414-4DA9070F255F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d05ad2eca69e3d05b0995efa644d8fb62fe57db","datavalue":{"value":{"entity-type":"item","numeric-id":2345629,"id":"Q2345629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3074b8ebfc51f89b1e3dcb59c2071e966af4ceb","datavalue":{"value":{"amount":"+0.8448347449302673","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":"Q2243141$F6842457-E6B1-4FA2-B4A0-EE8E8F564360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2abdee1cdbc7ff334c4291ce969d14f0ba52c3b2","datavalue":{"value":{"entity-type":"item","numeric-id":5174954,"id":"Q5174954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4f7211d207b912e2e990059f8b1fbba1a364ec4","datavalue":{"value":{"amount":"+0.8390517234802246","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":"Q2243141$468BF8F4-99B0-490A-BD55-48A4E83E942C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f176edcbb86d35f075dcde5b642e6e903cf6bd","datavalue":{"value":{"entity-type":"item","numeric-id":2906356,"id":"Q2906356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b17a75bd866f1133f61196731c90030f7ec8ee6","datavalue":{"value":{"amount":"+0.810838520526886","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":"Q2243141$C1AEA9E0-CD78-4E34-AF44-35591BEAD557","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2243141","badges":[]}}}}}