{"entities":{"Q5937606":{"pageid":8114408,"ns":120,"title":"Item:Q5937606","lastrevid":47640793,"modified":"2026-01-02T07:10:53Z","type":"item","id":"Q5937606","labels":{"en":{"language":"en","value":"On vertex orderings and the stability number in triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1619857"}},"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":"Q5937606$4C8E8985-135A-4CA1-B901-206CAF42B889","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"869bce511c9cf0d7ba23d24b897fb15c8f208e28","datavalue":{"value":{"text":"On vertex orderings and the stability number in triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937606$582554A1-A800-4428-A479-081C876529C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83648442457040e5b08b10213efb54a901467e88","datavalue":{"value":"0983.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937606$A028D013-AAAB-4F3A-9922-198ECD8E98B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d8109da989a6ad2c7028efdbb9044035fa66703","datavalue":{"value":"10.1016/S0012-365X(00)00335-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937606$D042E58D-827A-4A03-96CF-EDAC143BC85B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a76e14dae6cbb3abcd2d6da25c84b7ddc989b2f","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937606$941E4674-D7A2-47E2-854C-9CFA6C9F2721","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":"Q5937606$44CAD431-F613-4D87-8162-6489A84BAC13","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fdb5a504359c0d924879fd97edc82d8bdc42beac","datavalue":{"value":{"time":"+2002-04-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937606$C142E8C5-CFE8-48DB-9481-37B36C8AE82D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937606$041209E0-0986-41EB-A5DA-C61D036F3713","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937606$6895571A-8A82-4E42-BF65-7D897AC3626C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937606$18163E30-43CC-4389-AF5D-7CF156E94F99","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b96629eeadbf83d8110f1b3f2a739f25e71a5e35","datavalue":{"value":"1619857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937606$BA4A542F-CEFE-4243-9FBE-954B67E3E78A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfe6c8c21a5b7a8155109b3522d8e4ed82f42953","datavalue":{"value":"maximal stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$35008103-3A9E-42DB-B69B-95B6D54B593E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87e0e2197df31604dd9f16334c9c805616d74d2d","datavalue":{"value":"stability number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$3C1795AD-D1E7-4B4B-B793-82327162F530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$058B3491-E994-4737-84FD-93A968979A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$F4D8FECC-E533-42C8-A5FB-03399B13CFB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"938507bc54d83812726579a12a77d5cd2af4ae8b","datavalue":{"value":"triangle-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$7A3DC68F-85D6-4AE9-9BEB-4EBDD2E20931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f8854b5e4a0017c2e603242cf5eca1a042ef5e8","datavalue":{"value":"forbidden induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$11421B78-1045-416E-A6FF-42135168AC94","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":"Q5937606$0CDA6178-0B6C-42F7-8CFD-4A5DFD178F0A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"16e4619cf7194695c23429eea89cb241525dae4f","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00335-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q5937606$FC0AA81D-053E-48C2-AD2E-2AD4446FA9B1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c8b7b8fd3f3bfe4ff280b23f8afb277b0f1a0ab","datavalue":{"value":"W2073631490","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937606$A10323BE-4BF5-452A-A584-68C412ECD0BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f37229902635f72e3dd65cf22736b170fc86d91d","datavalue":{"value":"Let \\(G= G(V,E)\\) be a simple and finite graph. A set \\(S\\) of pairwise non-adajcent vertices in \\(G\\) is called stable. \\(S\\) is a maximal stable set in \\(G\\), if \\(G\\) has no stable \\(S'\\) with \\(S\\subset S'\\), and the cardinality of such an \\(S\\) is called the stability number \\(\\alpha(G)\\) of \\(G\\). A maximal stable set of \\(G\\) can be got by applying a certain algorithm, called greedy algorithm, on a given ordering \\(v_1,\\dots, v_n\\) of the vertices of \\(G\\). For this algorithm the vertices in the given order are to scan and \\(v_i\\) is to put in \\(S\\) only if no vertex \\(v_j\\) in \\(S\\) with \\(j< i\\) is adjacent to it. The cardinality of the stable set that arises in this way is denoted by \\(\\alpha(G; v_1,\\dots, v_n)\\). If \\(\\alpha(G)= \\alpha(G; v_1,\\dots, v_n)\\) then the ordering \\(v_1,\\dots, v_n\\) is called an \\(\\alpha\\)-ordering and it is known that the determination of an \\(\\alpha\\)-ordering of a graph \\(G\\) is NP-hard.NEWLINENEWLINENEWLINE\\textit{N. V. R. Mahadev} and \\textit{B. A. Reed} [J. Graph Theory 30, No. 2, 113-120 (1999; Zbl 0918.05086)] investigated two types of vertex orderings satisfying certain conditions (Property 1 and Property 2) and they characterized a class of graphs for which a maximum stable set can be computed in polynomial time.NEWLINENEWLINENEWLINEThe author gives a partial answer to a further question of Mahadev and Reed and he gives a complete characterization of all triangle-free graphs that have Property 2 (for every induced subgraph \\(H\\) of \\(G\\), every ordering of the vertices of \\(H\\) that is of the above shortly indicated Type 2 is an \\(\\alpha\\)-ordering) in terms of an infinite number of forbidden induced subgraphs; here a maximal stable set also can be computed in polynomial time. Three classes \\({\\mathfrak C}_1\\), \\({\\mathfrak C}_2\\) and \\({\\mathfrak C}_3\\) of graphs which contain these forbidden induced subgraphs are defined. \\({\\mathfrak C}_1\\cup {\\mathfrak C}_2\\cup{\\mathfrak C}_3\\) is denoted by \\({\\mathfrak C}\\). The following main result is proved: A triangle-free graph \\(G\\) has Property 2 iff it contains no graph in \\({\\mathfrak C}\\) as an induced subgraph (Theorem 1). The proof of this theorem is given by proving a more extensive structural result (Theorem 2) which implies Theorem 1.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937606$9C36F527-FEA7-4B96-B907-9ADF2FC6A430","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de653027042290273214d8e145e7e4ca0e2bf6de","datavalue":{"value":{"entity-type":"item","numeric-id":4229265,"id":"Q4229265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94d9f0f9e23a82f9e6a5434e464a80931cfd6eee","datavalue":{"value":{"amount":"+0.9021501541137696","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":"Q5937606$4150046C-AF77-4DAA-9B20-525385FFE37B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd03623aac3092152bd3c56f183a561747e14add","datavalue":{"value":{"entity-type":"item","numeric-id":1850112,"id":"Q1850112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94d9f0f9e23a82f9e6a5434e464a80931cfd6eee","datavalue":{"value":{"amount":"+0.9021501541137696","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":"Q5937606$F28E31D1-BC7A-4CF8-808B-847B86BDC203","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":"4e3b2ff8e653d21d5a93ba8f24816a7c3deca6b4","datavalue":{"value":{"amount":"+0.7740041017532349","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":"Q5937606$DC435A36-EA73-4B8F-B24A-917D16EE659E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31688eebc0069911c19d67ec2760a6fbd8f7772f","datavalue":{"value":{"entity-type":"item","numeric-id":1894362,"id":"Q1894362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2deb723fa7b07ce25ef05ec52c2762e0d527cd8d","datavalue":{"value":{"amount":"+0.7737784385681152","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":"Q5937606$A6DA8186-D4EF-4151-B9E9-A9221AB6AD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"043ebe8c5511ce9b0ca92f47f3b61ee143eeafeb","datavalue":{"value":{"entity-type":"item","numeric-id":1414595,"id":"Q1414595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5419aea7621ed277f1967aa9a24c27bf0096e2b3","datavalue":{"value":{"amount":"+0.7727472186088562","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":"Q5937606$C562C5B3-DE9B-4767-99FB-F3FB564C514B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937606","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937606"}}}}}