{"entities":{"Q5951946":{"pageid":8128748,"ns":120,"title":"Item:Q5951946","lastrevid":93486152,"modified":"2026-06-05T04:28:47Z","type":"item","id":"Q5951946","labels":{"en":{"language":"en","value":"The overfull conjecture and the conformability conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1687472"}},"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":"Q5951946$B08D2EE9-F129-45A8-A807-B6E59CAD9004","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40eb307709a507be27918bbd634ba29018bc98c7","datavalue":{"value":{"text":"The overfull conjecture and the conformability conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5951946$0D481730-4493-4DA0-841D-6A91967DBA12","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"53f493a45a8c52f92bc5d7a37728fcaaee713f75","datavalue":{"value":"0992.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951946$38937E25-093E-4705-84D1-975AECC79367","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ae1c419a851963317f74c78bd9cb28a16bf6974","datavalue":{"value":"10.1016/S0012-365X(01)00153-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951946$C124C934-8D2E-4B29-BE04-C68432278C03","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fed0fe195c7c30cec1ec29d1ddd1134cd27f289","datavalue":{"value":{"entity-type":"item","numeric-id":590704,"id":"Q590704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951946$5F70F8F9-B4A0-4011-95C3-B246F9BABC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fe4e44a81f66a2f8b7dfec014d36e832a2c77ff","datavalue":{"value":{"entity-type":"item","numeric-id":189742,"id":"Q189742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951946$C2F3A6EF-5802-458C-A344-07004D32B018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c76402894fbdb29ea18242f30748d63a500b2366","datavalue":{"value":{"entity-type":"item","numeric-id":221634,"id":"Q221634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951946$E6CD0DB2-0DBE-4EF2-BA05-FC797E55DA85","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":"Q5951946$F8A09730-6618-42F7-AF8E-6697BE7C8759","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"142362e6d8f26628ca200c5bf9158be42ab9f824","datavalue":{"value":{"time":"+2002-08-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5951946$9FA2D47E-18E1-4E3B-8B58-E78DAA7FFF16","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9a1bee4baae85f5dd41ed5d2abc7b83018db5d4","datavalue":{"value":"Vizing's well-known result that \\(\\triangle (G) \\leq \\chi '(G) \\leq \\triangle (G) +1\\) (where \\(\\chi '\\) denotes the chromatic index) led to the classification of a graph as Class 1 if \\(\\chi '(G) =\\triangle (G)\\) and Class 2 if \\(\\chi '(G) =\\triangle (G) +1\\). The overfull conjecture of \\textit{A. G. Chetwynd} and \\textit{A. J. W. Hilton} [Star multigraphs with three vertices of maximum degree, Math. Proc. Camb. Philos. Soc. 100, 303-317 (1986)] is Conjecture 1: If \\(G\\) is a graph satisfying \\(\\triangle (G)>\\frac{1}{3}|V(G)|,\\) then \\(G\\) is of Class 2 if and only if \\(G\\) contains a subgraph \\(H\\) with \\(\\triangle (H)=\\triangle(G)\\) and \\(|E(H) |>\\triangle (H)\\lfloor \\frac{V(H)}{2}\\rfloor .\\) The total chromatic number conjecture is that \\(\\triangle (G) +1\\leq \\chi _{T}(G) \\leq \\triangle (G) +2,\\) where \\(\\chi _{T}(G) \\) denotes the total chromatic number. If \\(\\chi _{T}(G) =\\triangle (G) +1\\) then \\(G\\) is called Type 1, and if \\(\\chi _{T}(G) =\\triangle (G) +2,\\) then \\(G\\) is called Type 2. A graph \\(G\\) is conformable if it has a vertex colouring in \\(\\triangle (G) +1\\) colours such that the number of colour classes with parity different from that of \\(|V(G)|\\) is less than or equal to the deficiency \\(\\sum_{v\\in V(G)}(\\triangle (G)-d_{G}(v))\\). The modified conformability conjecture [\\textit{G. M. Hamilton, A. J. W. Hilton} and \\textit{H. R. F. Hind}, CRM Proc. Lect. Notes 23, 43-98 (1999; Zbl 0943.05034)] is Conjecture 2: If \\(G\\) is a graph satisfying \\(\\triangle (G)\\geq \\frac{1}{2}(|V(G) |+1) ,\\) then \\(G\\) is Type 2 if and only if \\(G\\) contains a subgraph \\(H\\) with \\(\\triangle (H) =\\triangle (G) \\) which is either non-conformable, or, when \\(\\triangle (G) \\) is even, consists of \\(K_{\\triangle (G) +1},\\) with one edge subdivided. In this paper it is shown that under some fairly general conditions Conjecture 1 implies Conjecture 2. It is also shown that if \\(G\\) has even order and high maximum degree, then \\(G\\) is conformable unless the deficiency is very small.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951946$B652F4CC-2990-45A5-9280-6FD427642B65","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a442079b5f7b524052e3b9ba53793079a6d84fd","datavalue":{"value":{"entity-type":"item","numeric-id":266956,"id":"Q266956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5951946$4330D716-92EC-46FC-9D0C-B787C1263A8A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951946$49AACF80-0CCB-44E0-B1BB-AA46C0A2F723","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"00e897b5a88eedd1393a641d76d74cb56c91e858","datavalue":{"value":"1687472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951946$9C182846-0835-496D-9627-2318B5D24E46","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951946$9A883003-3347-4AF3-AB83-D329BB849337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc653b6a31dcd73ff0c82a090d57852e65c2467f","datavalue":{"value":"total colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951946$9BA2F208-871A-4909-9EDB-65AA3698C252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a71968711732e0fff452c236e59fcaf69ca7f216","datavalue":{"value":"overfull conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951946$F6471B2E-2A23-4BF5-9F57-C876F4A1A436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8dac5328c8369a1dad2c59b18e920f429cb3cd63","datavalue":{"value":"conformability conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q5951946$A4A8345B-1037-48AF-AA3C-90E854041405","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":"Q5951946$287AE5EA-7530-43D6-8DCD-A3481598A9E2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9392f710792a22867b9f9d68ed9d8a169a2993c3","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00153-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q5951946$024DA6BB-B2E0-4864-B9E7-1BA8298BE3A6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"700990650861bc92841f6953334f046bd3baa086","datavalue":{"value":"W2036964919","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951946$1406DCAB-833C-447F-84F7-50D9DC87D3C8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"845c069e713eb74f4639809fb105ce20daeb201d","datavalue":{"value":"Q128132550","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5951946$04DB1892-94BB-43A3-A424-DD0E29F19E1C","rank":"normal"}],"P1643":[{"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":"86a79586b392a73b9dcf44b6263c21af215fcc55","datavalue":{"value":{"amount":"+0.8918158411979675","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":"Q5951946$46DA4E98-A2C7-4221-8713-2700410CFB19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0bcf74e8ffe201266ee31715b87960de9c671e6","datavalue":{"value":{"entity-type":"item","numeric-id":4487450,"id":"Q4487450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f600009cdb44c27ac41af076a3cd6144d0b6ae32","datavalue":{"value":{"amount":"+0.8893542289733887","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":"Q5951946$E9B29077-37DC-4CDA-9B99-047C1F57F834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6468308c54c05e9697f9b941fd2e06848a25365c","datavalue":{"value":{"entity-type":"item","numeric-id":1849925,"id":"Q1849925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d159d1403227c1a7a4714a8171474923ffebbc30","datavalue":{"value":{"amount":"+0.8878400325775146","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":"Q5951946$0B9B56F1-0AF4-4E41-9572-6AA1E142D6B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57783eb8c9247758731eddbde6a27b6077b291b6","datavalue":{"value":{"entity-type":"item","numeric-id":4636270,"id":"Q4636270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de86198b6fc1e8100f3cdeb51504a051c4d4aa09","datavalue":{"value":{"amount":"+0.8858727812767029","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":"Q5951946$F30D6AE3-295C-474A-BFBF-0ADC34344E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53a741e2a72406c4f711eae8ba5ffb7d017a9737","datavalue":{"value":{"entity-type":"item","numeric-id":1090683,"id":"Q1090683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea2e4f81353ef313141b7438288a08c150c4892e","datavalue":{"value":{"amount":"+0.860744059085846","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":"Q5951946$47D2E0B5-31CC-4983-B3D3-A9B9A585C1D2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The overfull conjecture and the conformability conjecture","badges":[]}}}}}