{"entities":{"Q1594580":{"pageid":1605320,"ns":120,"title":"Item:Q1594580","lastrevid":47569132,"modified":"2026-01-02T02:40:33Z","type":"item","id":"Q1594580","labels":{"en":{"language":"en","value":"How to find overfull subgraphs in graphs with large maximum degree. II"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1560492"}},"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":"Q1594580$54DFEEC6-C217-4E88-97BE-5055A419B4A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a128b4b6631c4e370a6768f631add8b2e93eabe6","datavalue":{"value":{"text":"How to find overfull subgraphs in graphs with large maximum degree. II","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1594580$E6E64A75-308C-49C5-8684-EDBE44110FBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71b425f4441abad9f4263438423a88c8851125b2","datavalue":{"value":"0970.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594580$BA423C77-8D53-4F98-85DC-C6A67C9D328F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"47bd6754131a25a638ef3515065e1aa052ab72d5","datavalue":{"value":{"entity-type":"item","numeric-id":1298726,"id":"Q1298726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1594580$4A73B007-9C8E-4790-A9F0-0C6FDA67B62A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1594580$7399B3F6-F95A-4A1E-B332-6F72AB958D36","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1f254fdbb9fe00827c6b84e770ead83cb29ab1e5","datavalue":{"value":{"time":"+2001-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1594580$F973F67B-B2F1-4D49-891B-9D9B97E29087","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d8498b761ee94376f69d77a9048d7e62effee21d","datavalue":{"value":"https://eudml.org/doc/121258","type":"string"},"datatype":"url"},"type":"statement","id":"Q1594580$314B45CE-B427-4365-A743-0C8F31FB2894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d338b8e5e1874d85f213ba4533d1b2a1322e0f07","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r7.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1594580$7D1BFE32-FAAB-4BA8-9BF5-A42E457AD791","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f72adacd6029bf9f8b6432b4321cb24a6ac33961","datavalue":{"value":"[For Part I see Discrete Appl. Math. 51, No. 1-2, 117-125 (1994; Zbl 0805.05032).]   Let \\(G= G(V,E)\\) be a simple graph with \\(3\\Delta(G)>|V|\\). \\(\\chi'(G)\\) and \\(\\Delta(G)\\) be its chromatic index and the maximum degree of its vertices, respectively. \\(G\\) is said to be overfull, if \\(|E|>\\lfloor|V|/2\\rfloor\\cdot\\Delta(G)\\), and \\(G\\) is called Class 1, if \\(\\chi'=\\Delta\\), otherwise, \\(G\\) is called Class 2. It is known that \\(\\chi'= \\Delta+1\\) holds for every Class 2 graph. Every overfull graph is Class 2, as well as every graph \\(G\\) having an overfull subgraph with \\(\\Delta(H)= \\Delta(G)\\) (such a subgraph is called \\(\\Delta\\)-overfull). It can be shown that a graph \\(H\\subset G\\) is \\(\\Delta\\)-overfull iff \\(|E(H)|> \\lfloor{1\\over 2}|V(H)|\\rfloor\\cdot\\Delta(G)\\). An overfull graph conjecture, formulated in the literature, is stated, namely that a graph with \\(3\\Delta>|V|\\) is Class 2 iff it has a \\(\\Delta\\)-overfull subgraph. Whereas in Part I (in the course of the investigation of simple graphs with \\(2\\Delta\\geq|V|\\)) an algorithm for finding overfull subgraphs was presented, the main result of Part II is an algorithm which finds all induced \\(\\Delta\\)-overfull subgraphs of a graph \\(G\\) with \\(3\\Delta(G)>|V|\\).   Therefore at first the algorithm given in Part I, is modified such that it determines every induced \\(\\Delta\\)-overfull subgraph \\(H\\) of an arbitrary graph \\(G\\) with \\(|V(H)|>|V(G)|- \\Delta(G)\\) in \\(O(n\\log n+m)\\) time, where \\(n\\) and \\(m\\) denote the order and the size of \\(G\\), respectively, and this algorithm is called Algorithm 1 (Theorem 3.2). Moreover, the author receives a generalization of Theorem 3.4 in Part I, namely that every graph \\(G\\) has at most one induced \\(\\Delta\\)-overfull subgraph \\(H\\) with \\(|V(H)|>|V(G)|- \\Delta(G)\\) (Theorem 3.3). In the special case of simple graphs with \\(2\\Delta\\geq|V|\\) it follows that these graphs have at most one induced \\(\\Delta\\)-overfull subgraph, which can be found in \\(O(n+ m)\\) time (Theorem 3.4), and by this the former algorithm is improved to run in linear time.   To get the above-mentioned main result, Algorithm 2 is developed in three phases and Algorithm 1 is applied here occasionally. Moreover, two procedures for this problem are used, namely one for the general case and another for the regular graphs.   The author proves the following results: Algorithm 2 finds all induced \\(\\Delta\\)-overfull subgraphs of a graph \\(G\\) with \\(3\\Delta(G)>|V(G)|\\), they can be found on \\(O(n^{{5\\over 3}}m)\\) time and in the case of a regular graph in \\(O(n^3)\\) time, where \\(n\\) and \\(m\\) denote the order and size of \\(G\\), respectively (Theorems 4.3, 4.4, and 4.5). Finally, with the help of Algorithm 2, Corollary 4.6 can be deduced: A graph with \\(3\\Delta>|V|\\) has at most three induced \\(\\Delta\\)-overfull subgraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594580$AEC1A2D5-2B85-40C2-8497-0B3D6FDA1004","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594580$4955176C-38EC-4862-884A-8A9075514F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594580$C807C676-DD61-46E2-9610-7204E005D85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594580$DA476CC9-C93B-47D3-89FD-9ECF663FDF2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17bb69194a916d3744d4e741cf99a7e2e078ef6b","datavalue":{"value":"1560492","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594580$2C00293B-5F8E-4073-82EF-607D3A3A49FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594580$78C3F2D1-C718-4189-A501-E8E547F5CB6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594580$BEB7E85C-4C77-42EB-822F-982E4743F701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3a646df5588eeaf949d8deaaa60a3b79781c81d","datavalue":{"value":"overfull graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594580$093FEDCC-C19F-4939-ADB6-27518FDE0487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594580$4E423CB4-B355-46E7-BE38-D8E5001AE6BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1594580$7697D923-B9F2-4FE2-A2FF-8FDC7D3EAE70","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":"Q1594580$7A4DA3E2-2C9E-4549-84D2-298FB249D87F","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":"Q1594580$84EB3ADB-CD05-4B66-ABA7-179F57203C8C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b9a5ee57b1c415325d0ec0d263e9bf5228fb4e0b","datavalue":{"value":"bafkreihddt3z2kl6dttwrcyc3lppgt2ehvdi7n3ejakyypiq6bhcvh4xle","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1594580$5CAE4428-F5BE-446B-A2B8-E7F9BDAF8FB5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"554a0d0de0587ab4765f112ae8c84d0a876b43ba","datavalue":{"value":{"entity-type":"item","numeric-id":1329811,"id":"Q1329811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7072426f7b6d022aa53cb3072085b5cf31841f09","datavalue":{"value":{"amount":"+0.9651474952697754","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":"Q1594580$7F870920-804F-4506-8BA0-65CAAEC0C1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c28aed145a519d83e5bbcf20c589916729a8e6c3","datavalue":{"value":{"entity-type":"item","numeric-id":3159391,"id":"Q3159391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7072426f7b6d022aa53cb3072085b5cf31841f09","datavalue":{"value":{"amount":"+0.9651474952697754","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":"Q1594580$BF646335-E981-491D-9836-67D55E8F624A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b8b3d7985b4db256e76e46d5cb123a51c655311","datavalue":{"value":{"entity-type":"item","numeric-id":6094039,"id":"Q6094039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a7eca95f1b6a5e5a932f8f18e306bc928360627","datavalue":{"value":{"amount":"+0.8606890439987183","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":"Q1594580$30EF8AB7-FBD4-4A05-90E8-880ED456C387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8640bc0b4c7fadc915712b5b1269865a0da104a3","datavalue":{"value":{"entity-type":"item","numeric-id":5866456,"id":"Q5866456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e380524d4398ab332176a509ad6de7ef5cc2c57b","datavalue":{"value":{"amount":"+0.8450291156768799","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":"Q1594580$F96B287E-4289-4F6A-BB29-EDEC15BD2F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eb948367f5b060b2de943692bf36505d297801f","datavalue":{"value":{"entity-type":"item","numeric-id":3976633,"id":"Q3976633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d788b03782c1aa0d0ed5a78858aedbbd9c7a244","datavalue":{"value":{"amount":"+0.8385844230651855","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":"Q1594580$38D10C17-5034-44A7-9367-3FAAB9F2EC7B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1594580","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1594580"}}}}}