{"entities":{"Q790826":{"pageid":792674,"ns":120,"title":"Item:Q790826","lastrevid":64366137,"modified":"2026-04-11T19:23:02Z","type":"item","id":"Q790826","labels":{"en":{"language":"en","value":"Regular graphs and edge chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3849255"}},"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":"Q790826$493FAD77-69C4-4AFF-ABF3-92754F6F50EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0d415da1e82b7b52fcd85c6376fab9816f2e43fe","datavalue":{"value":{"text":"Regular graphs and edge chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790826$640A9D64-A372-43A9-9640-106E595867FE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fc5beca36fda4ea87876abb7d33715e78b6a3a84","datavalue":{"value":"0535.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790826$9E0D1E4A-2B0F-4B20-A879-D76252C2B430","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81bc4960297bc5399c9195dd52a89e8573307623","datavalue":{"value":"10.1016/0012-365X(84)90182-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790826$4B35EBD0-715D-4EC3-8E92-376FEBD41809","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":"Q790826$314C359A-3853-41B4-9B06-8DCFB555EC26","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q790826$FA7D9BC4-E012-48E3-B8D3-51236D7B3347","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"314ec644ac43500425d117bcadecd4e5c23e400a","datavalue":{"value":"For a simple graph \\textit{G. Vizing}'s Theorem [On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3, 25-30 (1964)] implies that \\(\\Delta(G)\\leq \\chi(G)\\leq \\Delta(G)+1,\\) where \\(\\Delta\\) (G) is the maximum degree of a vertex in G and \\(\\chi\\) (G) is the edge chromatic number of G. It is, of course, possible to add edges to G without changing its edge chromatic number. In fact, any graph G is a spanning subgraph of an edge maximal graph \\(G^*\\) such that \\(\\chi(G^*)=\\chi(G)\\). The question addressed here is when there exists such a graph \\(G^*\\) which is \\(\\chi\\) (G)-regular.    Theorem. If \\(n\\geq 2(k^ 2-k+1),\\) n is even, \\(k\\geq 2\\) and G is a connected k-regular graph with n vertices, then G is a spanning subgraph of a \\((k+1)\\)-regular graph \\(G^*\\) with \\(\\chi(G^*)=k+1.\\)- Conjecture. If \\(n\\geq 2k\\), n is even, \\(k\\geq 2\\) and G is a connected k-regular graph with n vertices, then G is a spanning subgraph of a \\((k+1)\\)-regular graph \\(G^*\\) with \\(\\chi(G^*)=k+1\\) except when \\(G=K_{k,k}\\) and k is odd.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790826$7F435793-0C77-40BF-A48B-FFA77E80382B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790826$5989E2F2-A3CB-48CD-9A4D-DE1BEF1D4D7C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee333477ec35e7c3d347e4e51f5a4e71327aeb21","datavalue":{"value":"3849255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790826$D7DE0B9E-BD27-428A-A32A-0098CB581807","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q790826$DD798834-3DC6-47E5-8EBF-83401F827793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5de15a9b74a73ed49559247867f1e4cf37f69c9b","datavalue":{"value":"edge chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q790826$EA9BA516-FF6F-4768-8C41-9B5CB42A34AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bcb88e4835cfef6b70b1d60481bd40424864103","datavalue":{"value":"spanning subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q790826$92CA5DAC-836A-4DFD-85BC-E14D877FA87C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a90237f4fbe17f8aa89942b7417b8396bf1098f7","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$BB413258-8657-4224-BBB1-8D081066D17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a10015d8dc84d50c1e5f084a7e3b6881a3686835","datavalue":{"value":{"entity-type":"item","numeric-id":420624,"id":"Q420624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$E4D99CB6-5CBE-4849-9487-4F9742B768ED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c373609087678f84cf49ac586680a31002124e72","datavalue":{"value":{"entity-type":"item","numeric-id":267204,"id":"Q267204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$8C33C5C5-123F-4681-9475-6C7DA60A9661","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":"Q790826$AA21E1C5-6939-4325-889D-F931302E0B19","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa6b88d7c0c035ddcdc73a99f8a04d3f8ce9fbcc","datavalue":{"value":{"entity-type":"item","numeric-id":4187840,"id":"Q4187840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$708E186C-D279-4B19-BA08-D8EDABCF8861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$814680D1-6169-4931-9D24-B6ED6DD02552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1474ad965005531fc787ddda571bd10843eacd","datavalue":{"value":{"entity-type":"item","numeric-id":3853641,"id":"Q3853641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$ADAA12AF-649E-46F6-B38D-DF8E14CD10C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfba955c32dc153431f5c99ab1d6a49daa930c11","datavalue":{"value":{"entity-type":"item","numeric-id":5785127,"id":"Q5785127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790826$5678715E-60D5-4481-AB0D-714251D070A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fca6eb97fe924b980478ffda19c56303280caac5","datavalue":{"value":{"entity-type":"item","numeric-id":2465629,"id":"Q2465629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed514a20ae29ae33e16f2cfccdcd2d453ab41625","datavalue":{"value":{"amount":"+0.8488056063652039","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":"Q790826$215DDC84-2DE5-4E3A-8E11-96A09C2B016B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7593fc8421989335b9d42aa6a93160ed2d399b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3470480,"id":"Q3470480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93e4bfce603c1c40246080b464bf0e7399885ff3","datavalue":{"value":{"amount":"+0.8397582769393921","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":"Q790826$B239FD9E-5BEC-4213-80F8-62D50F02D424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52bb794b98e0ed0527a513225a30c43bc2305175","datavalue":{"value":{"entity-type":"item","numeric-id":1356779,"id":"Q1356779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb23ec5e98fd639f713962b8101115fa7a6c25ea","datavalue":{"value":{"amount":"+0.8357179164886475","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":"Q790826$DD90AAB4-90CB-492E-B0CA-F2E9ADB4F79A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a248444e1636f1955c0057ebc8fd42a7b64b0354","datavalue":{"value":{"entity-type":"item","numeric-id":910411,"id":"Q910411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c1c92c1fe0b865c8e92e3678cd72c67ca4908eb","datavalue":{"value":{"amount":"+0.83500075340271","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":"Q790826$527E602E-9798-4879-932C-90BADC60A7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cfb957f2db9db99d43ff6a5d9536b1758e530b4","datavalue":{"value":{"entity-type":"item","numeric-id":1123197,"id":"Q1123197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3abb6a992dd50a818f44d1c2bdb858246133a973","datavalue":{"value":{"amount":"+0.8330755829811096","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":"Q790826$25A87367-5E73-4D6E-9A61-CC4F46E46293","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Regular graphs and edge chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Regular_graphs_and_edge_chromatic_number"}}}}}