{"entities":{"Q653987":{"pageid":655836,"ns":120,"title":"Item:Q653987","lastrevid":63353568,"modified":"2026-04-11T12:18:16Z","type":"item","id":"Q653987","labels":{"en":{"language":"en","value":"The structure of hereditary properties and 2-coloured multigraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990944"}},"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":"Q653987$B3C0B202-A993-4C15-9D6C-2BC6B6E7417E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1e80214c9121e9a9b9d9cdd43783a50e8cd9972","datavalue":{"value":{"text":"The structure of hereditary properties and 2-coloured multigraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653987$7F2569D8-67D0-4690-B731-EC1A94D04C0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db1034ef7e6631bb5a9f359c72ebf3dc22be5d2d","datavalue":{"value":"1249.05200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$4D80DFD0-EFD5-4511-9D1C-29D214F0B48C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a7b894690b9c24168125b136d60e5c3297a3bc5","datavalue":{"value":{"entity-type":"item","numeric-id":653986,"id":"Q653986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$7002DDB1-8594-4531-BDB8-583BA5488108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bde2140b5b5ce5800790e0742b7d8b3fabb665a6","datavalue":{"value":{"entity-type":"item","numeric-id":1253258,"id":"Q1253258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$62B91969-CAE8-4BD2-A301-1516AFD7F366","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$341C3CFC-F3B9-42BB-AE6B-7FE67C23094E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9a9ebdc8bdc44c407c473bf89fbe244ce057f32","datavalue":{"value":{"time":"+2011-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q653987$9C7DE974-8676-4FEE-89F6-77CDCF164CF4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"499ad823d0b5086e01a6c1c9e68b6ec03570bd04","datavalue":{"value":"A graph property \\(P\\) is a class of graphs closed under isomorphism; it is hereditary if it is closed under the taking of induced subgraphs. It is customary to say that graphs in the class \\(P\\) ``have the property \\(P\\)''.   \\textit{B. Bollob\u00e1s} and \\textit{A. Thomason} [Combinatorica 20, No. 2, 173--202 (2000; Zbl 0959.05105)] studied the probability of a hereditary property \\(P\\) in the probability space \\(G(n,p)\\). They found simple properties that closely approximate \\(P\\) in this space, and using these simple properties they determined the \\(P\\)-chromatic number of random graphs.   A hereditary graph property \\(P\\) can be associated with a class of 2-coloured multigraphs. Given a graph \\(G\\), let \\(cc(G)\\) be the complete 2-coloured multigraph with vertex set \\(V (G)\\) in which the edges of \\(G\\) are coloured red and the edges of the complement of \\(G\\) are coloured blue. Then, given a property \\(P\\), let \\(H(P)\\) be the class of 2-coloured multigraphs defined by \\(H(P)=\\{cc(G): G \\;\\text{not in}\\;P\\}\\). Note that every hereditary property \\(P\\) can be described by a family of forbidden (induced) subgraphs.   In this note the authors show that the analysis of hereditary properties in \\(G(n,p)\\) can be made more exact by means of the extremal properties of 2-coloured multigraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q653987$CC6E87D1-C548-46E8-BED3-31D5A9BA8127","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bf98c249556a3cbdf1ccaf58ec85cdce76ec514","datavalue":{"value":{"entity-type":"item","numeric-id":593214,"id":"Q593214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$5C917D68-AE28-4BCA-87DD-D35D8EB887CB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$CF54A349-F8C9-47FF-AF67-D0E451C4AE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$EE038524-5C3E-410E-A1E7-9CE778C2018D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$0443CAF6-3A54-4472-85B8-7C379BC9A924","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35fddc79fe4f1d19f1f203de6a90bfb7fbdf5112","datavalue":{"value":"5990944","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$58D38B56-4A40-4AF6-BA9B-6ADBE6F7318C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f024f3ed5c37bb9ef1b1544f3e9177ddad08a0b","datavalue":{"value":"hereditary graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q653987$9A5E0CDD-B7FE-4C64-B294-DCB9891A767F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e006c4eda23b49862f9f1b1cc0edf628584efea3","datavalue":{"value":"extremal properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q653987$4AD5B1A8-3412-428C-B6F9-B1EBE63AFF3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d9ffe43467d7c40a153180238070b49f713cfbc","datavalue":{"value":"2-coloured multigraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q653987$A36BCFE4-D080-4AC8-A047-424E4D636EB3","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":"Q653987$2F2EFBC3-8FAE-4A54-AE0D-1911964BAA58","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be295d8bce88b27b58cb39fcdd8021a11f796365","datavalue":{"value":"https://doi.org/10.1007/s00493-011-2630-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q653987$BBBEE890-7CE7-4BCC-AA11-F2D79B3D362B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"664c9a59d11a714b66297023be789dfbcc7ff7ca","datavalue":{"value":"W1993010909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$B4B58657-6FEC-4665-916A-08DA69A9432A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c984d6c9728273ad55f676642fad430507e25b8c","datavalue":{"value":{"entity-type":"item","numeric-id":4029804,"id":"Q4029804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$CFC48456-EB46-4D5B-A1DE-9D9CCB2571F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363111af09145596e6aa5e7da6afa9e1eeef3376","datavalue":{"value":{"entity-type":"item","numeric-id":3522831,"id":"Q3522831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$BA15987F-70A4-4C1D-8421-EC753A46E185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c451e7676cdd493b5d82e2ca3a9a5cf8a1def560","datavalue":{"value":{"entity-type":"item","numeric-id":3506314,"id":"Q3506314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$14054ED0-B31D-43CB-A523-EDBEBD17BD7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15c11964a2e71cdc829cd58513f856cd5a63935","datavalue":{"value":{"entity-type":"item","numeric-id":1010726,"id":"Q1010726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$AB8D8C3A-90CF-46B2-8F42-41E7ADE9205D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a704198da27f51a523769de240a677b950b9d5ff","datavalue":{"value":{"entity-type":"item","numeric-id":4863823,"id":"Q4863823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$008C3F5E-29DF-47C4-808D-2FB8E71E42C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c3f3c18d3012339c8ea8fa516e6cb0de7e130f","datavalue":{"value":{"entity-type":"item","numeric-id":5688999,"id":"Q5688999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$55EB6E38-6FF4-4950-8FCE-2F4B56ED7642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0893f06f165134598a1fdbebb0666712d7a2e96b","datavalue":{"value":{"entity-type":"item","numeric-id":5928567,"id":"Q5928567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$539469FC-C02B-46D8-ADB4-4F86EFB5B3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ca2deb622e66d040141c5d3946d3754cbb145c9","datavalue":{"value":{"entity-type":"item","numeric-id":2557710,"id":"Q2557710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$B5582B0A-7366-41D7-B25A-20DFD84E6996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"503a4b8853443cb392ecb2144b4e8e2121e2740c","datavalue":{"value":{"entity-type":"item","numeric-id":3745867,"id":"Q3745867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$3CF7B539-4096-4CAB-BBEC-74633E539F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbac1f4f76c6a914430e20bbd6820f01046ec5c3","datavalue":{"value":{"entity-type":"item","numeric-id":3060864,"id":"Q3060864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$C1AEC980-63CD-4314-9EAD-58AEF239F501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b95d02017a23858d35a70a4a89a5afae95fa2c21","datavalue":{"value":{"entity-type":"item","numeric-id":4273843,"id":"Q4273843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653987$0C9B1694-7B0F-4041-82BC-B9BEF8C5E476","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81d33c6e543db3311376fcfeeec14ea5e18318a5","datavalue":{"value":"10.1007/S00493-011-2630-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653987$06732018-61CD-4059-8991-787086D10BD6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b4f9c39b5ddda0c8320f8710b71c672f3b5af44","datavalue":{"value":{"entity-type":"item","numeric-id":6098071,"id":"Q6098071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e59caa712a4e5b03aaf91ea71598728982ec00b","datavalue":{"value":{"amount":"+0.8417208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$9D1EF295-18DA-4B06-BDFF-1A6E656525BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a007aabffda53c1367a3a8e2fc756f581615d052","datavalue":{"value":{"entity-type":"item","numeric-id":631643,"id":"Q631643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c250b1d7d57cfcebfe4ef5ca7041d5cb15376837","datavalue":{"value":{"amount":"+0.78605026","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$6BC0ED6F-52EB-4E09-B2C3-C26293BBF49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fc8e78f45a8ec53e345eccfa815d9daf74126f1","datavalue":{"value":{"entity-type":"item","numeric-id":3748295,"id":"Q3748295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2626579766bba090c14762aea6f01e100ae22c2","datavalue":{"value":{"amount":"+0.78398937","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$EFEC29A0-B0A7-4C93-A239-A25CCA347E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91acfa0c4763e57fde978254ff01f318ee43ddfd","datavalue":{"value":{"entity-type":"item","numeric-id":3989013,"id":"Q3989013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"023ab2a5093720d5d1d20119e9771557ef082bcf","datavalue":{"value":{"amount":"+0.7827562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$0FC250C4-3310-45E8-B5E6-FB20A6722FC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ff134eb4ede0b7cebb8030c5127b9e780cac5e6","datavalue":{"value":{"entity-type":"item","numeric-id":3797229,"id":"Q3797229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49384b629d58bd5316091a0d6330901fe5c4c64a","datavalue":{"value":{"amount":"+0.775627","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$58AD7990-6468-4258-B1EB-F180266C5684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae61c6e11c8124f5c34a4bb8d3fe3a53b14386d3","datavalue":{"value":{"entity-type":"item","numeric-id":1126826,"id":"Q1126826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83a181e7b642950ea6c33fd53de2fb988794fe82","datavalue":{"value":{"amount":"+0.77463233","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$36E08021-C13C-40E9-9888-24CDB095E1F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcb6b3fb76a1b66642c422ca77d56f48082c73ed","datavalue":{"value":{"entity-type":"item","numeric-id":5928567,"id":"Q5928567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbec2583a26eee5b4caf1176a40c4676dfbceaee","datavalue":{"value":{"amount":"+0.7684722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$4BC222C3-52CB-46A8-899A-A3B0CB822804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0cac736309be93d16eb51484eb021f9401debb","datavalue":{"value":{"entity-type":"item","numeric-id":4697825,"id":"Q4697825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5645baf6bfcb80ae0b0e11782f65e1c48d9f99e","datavalue":{"value":{"amount":"+0.76004285","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653987$AC5F0A5F-7725-44B5-8286-8E5A9CFED8C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The structure of hereditary properties and 2-coloured multigraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_structure_of_hereditary_properties_and_2-coloured_multigraphs"}}}}}