{"entities":{"Q868369":{"pageid":870217,"ns":120,"title":"Item:Q868369","lastrevid":64959702,"modified":"2026-04-11T23:23:08Z","type":"item","id":"Q868369","labels":{"en":{"language":"en","value":"On invariants of hereditary graph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5130456"}},"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":"Q868369$F4AAB815-74B0-43DA-B3F2-FCEDB9867940","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3860f03578f5ac8ebb1304d1c7196c1852e296db","datavalue":{"value":{"text":"On invariants of hereditary graph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q868369$876BCB2F-0F85-42EF-8FF4-DD4D8E91CC46","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ed00b52a0046ea6268acaf3130d83d83ede91de","datavalue":{"value":"1116.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868369$C3622129-6236-4598-A3F4-8DCBF9AD55F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4036c6045c03ed1b8266468de44b66130e5cf465","datavalue":{"value":{"entity-type":"item","numeric-id":237418,"id":"Q237418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$4EEA77D7-E00C-45E7-A9B0-B7568AEC06CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1cc1ac044203f0013b2ef0778c29a0cf2375b0c8","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$A91AA125-6D50-416C-B40F-AC00B5399992","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":"Q868369$C492415B-615D-45E6-8670-5B05414234FC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3af4457e51d097fa27d84537ba93ffccbacd245f","datavalue":{"value":{"time":"+2007-03-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q868369$853E95CE-BDF4-4E0E-A68D-5AFEE3358E38","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d1ae6366afef75f6f975d78c87b56e2f0ccca13","datavalue":{"value":"A hereditary property of graphs is a class \\(\\mathcal{P}\\) of graphs that contains all isomorphs and subgraphs of its elements. Such a property is determined by its minimal forbidden graphs, those graphs that do not belong to \\(\\mathcal{P}\\) but whose proper subgraphs all do. If \\(\\mathcal{P}\\) and \\(\\mathcal{Q}\\) are graph properties then their product \\(\\mathcal{P}\\circ \\mathcal{Q}\\) is defined by: \\(G\\in \\mathcal{P}\\circ \\mathcal{Q}\\) if \\(V(G)\\) can be partitioned into two subsets \\(V_{1}\\) and \\(V_{2}\\) with corresponding induced subgraphs \\(G_{1}\\in \\mathcal{P}\\) and \\(G_{2}\\in \\mathcal{Q}\\). If \\(\\varphi \\) is an integer-valued invariant of graphs and \\(\\mathcal{P}\\) is a hereditary property then \\(\\varphi (\\mathcal{P})\\) is defined to be the minimum value of \\(\\varphi \\) on the minimal forbidden graphs of \\(\\mathcal{P}\\). Under certain natural conditions, the authors characterize the invariants which are additive (i.e., \\(\\varphi (\\mathcal{P}\\circ \\mathcal{Q})=\\varphi ( \\mathcal{P})+\\varphi (\\mathcal{Q})\\)) for all hereditary properties \\(\\mathcal{ P},\\mathcal{Q}\\). They use this characterization to show that the degeneracy number and the tree-width are both additive with respect to hereditary properties.","type":"string"},"datatype":"string"},"type":"statement","id":"Q868369$406569AC-7AEE-44B3-BB13-6EABBB549C8B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"62a84c266ece164d73457a1cb4c4fa60144c1833","datavalue":{"value":{"entity-type":"item","numeric-id":329555,"id":"Q329555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$87B59479-540D-4C84-BE90-C41672AF0D54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868369$1BF8BC85-D40E-40E0-943F-744193332059","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b458fb0655971f992c7496ec4662eaab60a973a","datavalue":{"value":"5130456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868369$2CFB1CB5-D608-4316-B5B2-7F705BCD44DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ba298a428a6aad3d63de4c8fd42f73bd4f916dc","datavalue":{"value":"monotone graph invariant","type":"string"},"datatype":"string"},"type":"statement","id":"Q868369$90C0DCEB-28FE-470F-A2E1-C22B9E41AC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q868369$39A562B0-9E21-4804-A6CB-E77F5DE1C1C9","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":"Q868369$FF2D0DB8-9286-4F21-8421-A4AE0CC6C8FD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6152b1d88673a49930e20522b0be54996201d9a1","datavalue":{"value":"https://doi.org/10.1016/j.disc.2005.11.048","type":"string"},"datatype":"url"},"type":"statement","id":"Q868369$582BE543-8B7A-44B3-A52E-5173575D4F9B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb5b543216a01b92aca1cec27d83173d279f4541","datavalue":{"value":"W1964117141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868369$87A77174-BAAB-43C9-ACDA-C9ED67EA8951","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8227a98ad58b650f3b9e0772ff29bfad17b54f7","datavalue":{"value":{"entity-type":"item","numeric-id":2773047,"id":"Q2773047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$5726227D-D365-43FD-BE3D-59BBA1B77527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf199cfe008869511237b75edf119c1e10c4fe32","datavalue":{"value":{"entity-type":"item","numeric-id":4209931,"id":"Q4209931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$CCD73961-6362-458B-A119-325144B1B373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0ccfe2dfa7a23b5d70c67b8211ac83432ea610","datavalue":{"value":{"entity-type":"item","numeric-id":1307308,"id":"Q1307308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$5CF2CDED-4B3C-4EB4-9443-E1A85AAFA358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f8cc5bb26a839987158e049cf15d63a9fb81388","datavalue":{"value":{"entity-type":"item","numeric-id":4071280,"id":"Q4071280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$C3DC5DD8-4A07-4BE7-9DBB-0E1DAEB6B6A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe52f2805d4f9b4df7dc0389ff566736faca2767","datavalue":{"value":{"entity-type":"item","numeric-id":1883661,"id":"Q1883661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$140F97E3-29D9-4943-BB37-1B462D282D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$5540F67B-1A96-49CF-ACAB-6798BA11AE30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb44fa19ef432ebe70a929dc7ab6c3c9375a250","datavalue":{"value":{"entity-type":"item","numeric-id":3722536,"id":"Q3722536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$9DCF00F2-E461-4C9E-B7F2-5DE2ACA44AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e318d910ffc03c0417111417c16961fcd82befdd","datavalue":{"value":{"entity-type":"item","numeric-id":4159404,"id":"Q4159404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$DA372FE4-71CC-4C1B-9814-EC4A68B570FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"956f1c5b38c6fb926c10d5d61f8d6add606d90ad","datavalue":{"value":{"entity-type":"item","numeric-id":5959107,"id":"Q5959107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$3AEC506D-0FB4-41AF-A700-6E4D446B0E61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d779bde3b585ecc7a49f0adaac4822e26af55e","datavalue":{"value":{"entity-type":"item","numeric-id":4825849,"id":"Q4825849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$76C0948A-EDDF-4B5A-852F-874F90ACBFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ac5adfb1ff81241236798656acf26a3fd41c844","datavalue":{"value":{"entity-type":"item","numeric-id":1883266,"id":"Q1883266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$E15C1A9A-CE46-4288-BB08-9C604DB3993E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b19aad2c9a72e95f9350690ebb4e9aac1c6c708c","datavalue":{"value":{"entity-type":"item","numeric-id":3312262,"id":"Q3312262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$C6F3B716-2CE3-41DB-8F6D-D8CF6B3EF333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8124ef3d26284f7984fd987528796f2ab26730a3","datavalue":{"value":{"entity-type":"item","numeric-id":4264553,"id":"Q4264553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868369$7EF7D1A7-0BFD-4928-B6CC-E1D0F675E9C4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a2f1eddd82b5128df6331ab15137ebef90c2739","datavalue":{"value":"10.1016/J.DISC.2005.11.048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868369$F5B3B6AB-351A-43A4-913E-4F0C7EFD8CDC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f164cee695eec1b9b382165911aa98d0712c333a","datavalue":{"value":{"entity-type":"item","numeric-id":2725192,"id":"Q2725192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8abfb255d3ff9c584e9efde70598af1e0bb5723b","datavalue":{"value":{"amount":"+0.8496754169464111","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":"Q868369$B4F2579A-E274-494E-B0F2-FFC33235A1C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3404ab3b6e7d45fb1b02182f8446745f5ac1b296","datavalue":{"value":{"entity-type":"item","numeric-id":4680401,"id":"Q4680401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a56d1caec942ad052ed74103dc11c0dede810feb","datavalue":{"value":{"amount":"+0.8413407802581787","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":"Q868369$742E6D30-E134-4929-A154-F5EF7F72CCF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"212868caaec8267e80546060d779d012eefef8e0","datavalue":{"value":{"entity-type":"item","numeric-id":4846681,"id":"Q4846681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a9e8e11097c96509b3c4977caa9438ef16d8e3b","datavalue":{"value":{"amount":"+0.838249921798706","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":"Q868369$B70BDF05-5B56-46F5-ACF3-7C11DC088F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcef0f134f5fbb492de0df076938d5cbd6a7e5c9","datavalue":{"value":{"entity-type":"item","numeric-id":4944685,"id":"Q4944685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abf1d84a5f471dfa234d9fd371b595a94ca7f4cb","datavalue":{"value":{"amount":"+0.8346021175384521","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":"Q868369$9EDC4C53-4278-41DB-9F0E-E455F9F5B3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1efa2f4fcdd210d754653e797502ea09e37e1015","datavalue":{"value":{"entity-type":"item","numeric-id":4209932,"id":"Q4209932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de447ecd509c5c4cfd06c76fa145114dd4a9a5df","datavalue":{"value":{"amount":"+0.8319965600967407","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":"Q868369$319F5BEC-3957-4369-9B8D-3B8C1FABC910","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On invariants of hereditary graph properties","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_invariants_of_hereditary_graph_properties"}}}}}