{"entities":{"Q1893175":{"pageid":1903917,"ns":120,"title":"Item:Q1893175","lastrevid":69206427,"modified":"2026-04-13T05:28:14Z","type":"item","id":"Q1893175","labels":{"en":{"language":"en","value":"Generalization of two results of Hilton on total-colourings of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 769315"}},"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":"Q1893175$BB5A2263-64C2-4549-AE49-83794A9DEFEC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14c388567b8f28ef62d293cdde3245a3542ffeb5","datavalue":{"value":{"text":"Generalization of two results of Hilton on total-colourings of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1893175$BBCC5363-5AB0-4754-AAD9-63F7F6260D41","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0a63e0f95e18a2386166978a69a8c8210ad0775","datavalue":{"value":"0824.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893175$88BD3B51-B4CE-4AE0-B0F0-A06EC2401A84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9fb3fee367b1e305b059edcfad5583c34e64b9ef","datavalue":{"value":"10.1016/0012-365X(94)00291-P","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893175$11271B26-2FCB-4D4F-A8DA-4734EB671283","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":"Q1893175$8C9AF4DF-9C4A-4C96-ADDA-0680FDDFC124","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"870f54d3b5c36ab024bbe86b2f4a8332983cee6c","datavalue":{"value":{"time":"+1995-11-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1893175$8BD5A026-CFC0-448A-94A1-0AB90785A4DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2153bcb6afe9b08c4e8f08aaaa1afcfa383a6f63","datavalue":{"value":"A total colouring of a graph is a colouring of the vertices and edges such that no two adjacent vertices or edges get the same colour and no vertex gets the same colour as an edge incident to it. The total chromatic number \\(\\psi_ T(G)\\) of a graph \\(G\\) is the smallest number of colours with which \\(G\\) can be totally coloured. In [\\textit{A. J. W. Hilton}, A total-chromatic number analogue of Plantholt's theorem, Discrete Math. 79, No. 2, 169-175 (1990; Zbl 0714.05025)] it was shown that if \\(G\\) is graph with \\(2n\\) vertices and maximal vertex-degree \\(\\Delta(G)= 2n- 1\\), and if \\(\\psi_ T(G)= 2n\\), then \\(e(\\overline G)+ \\alpha'(\\overline G)\\geq n\\), where \\(\\overline G\\) is the edge-complement of \\(\\overline G\\), \\(e(\\overline G)\\) is the number of edges of \\(\\overline G\\) and \\(\\alpha'(\\overline G)\\) is the size of a maximal matching in \\(\\overline G\\). In the article under review, it is shown that for any graph \\(G\\) with \\(2n\\) vertices, \\(e(\\overline G)+ \\alpha'(\\overline G)\\geq n(2n+ 1- \\psi_ T(G))\\), from which the result in the aforementioned paper and several other known results are derived as special cases. In [(\\(*\\)) \\textit{A. J. W. Hilton}, The total chromatic number of nearly complete bipartite graphs, J. Comb. Theory, Ser. B 52, No. 1, 9-19 (1991; Zbl 0743.05022)] the following result is obtained. Let \\(J\\) be a subgraph of the complete bipartite graph \\(K_{n,n}\\) and \\(G\\) be the graph obtained from \\(K_{n,n}\\) by deleting the edges of \\(J\\). If \\(\\Delta(G)= n\\) and \\(e(J)+ \\alpha'(J)\\leq n- 1\\), then \\(\\psi_ T(G)= n+ 2\\). In the article under review, it is shown that, for \\(J\\) and \\(G\\) defined as in (\\(*\\)), if \\(\\psi_ T(G)= t\\) then \\(e(J)+ \\alpha'(J)\\geq n(n+ 2- t)\\), from which the result in (\\(*\\)) and a new one are derived.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893175$E2762E1A-7527-4B57-B358-13A0F754D6E4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893175$016595AE-ECA1-4E2F-B6FA-EC73C38AB12E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3164299a3873ee57841e0f0056d7d192ef35bbd","datavalue":{"value":"769315","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893175$AE4B0752-70FC-48F8-AFC9-F2B4D4ADFDF8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea63f40e565dc1f9f0c9457239edf3809e555071","datavalue":{"value":"results of Hilton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893175$3A70E44B-5314-48A6-B484-D243F854E03D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc653b6a31dcd73ff0c82a090d57852e65c2467f","datavalue":{"value":"total colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893175$93DEC5C0-E562-498E-BB73-3E8C0E4A85FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"917eb44fe6d809e0bc9389e0c20d8b3e6f0da35b","datavalue":{"value":"total chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893175$3BD55B2A-D377-4E8A-9C03-C94211D713D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4621396570425e2b0396722014057849131f6c8","datavalue":{"value":"maximal matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893175$58C45A4C-8CC6-4303-9C84-67A81778623E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2327e7151e7d3698818802619dca37a46fac53d","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$15DC7ABF-0008-4D65-9A79-21C3E4DBE985","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$8738FFCB-F6D0-4074-8178-822E7A533336","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":"Q1893175$89F727DA-9E69-4561-B9D7-A9E96AD9EC65","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a18decd282151f0c50f68615d322424f0bc10cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5621372,"id":"Q5621372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$C0F51915-31F3-4023-B4EA-F4B3F40E2442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f40853af1003ba07ffa89dfac6d0d1426014685a","datavalue":{"value":{"entity-type":"item","numeric-id":4044597,"id":"Q4044597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$C48107E8-DFF2-4678-961B-86D39BE675E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b46af0c24c5b819f022ee0a7dee2b7837902b3e1","datavalue":{"value":{"entity-type":"item","numeric-id":1196563,"id":"Q1196563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$2A3B53D4-3F02-465A-AB89-0F2A47CDCC03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e046cd759978bdb9679b6e987b2a3abde699df87","datavalue":{"value":{"entity-type":"item","numeric-id":4016026,"id":"Q4016026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$EDF0D878-85A3-4815-8B14-206BC347B828","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c59e9009a033e7d7ce19efa8fea7d29df2a1dc3","datavalue":{"value":{"entity-type":"item","numeric-id":1318798,"id":"Q1318798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$8B701475-348E-4CEA-A50B-B6939164560A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3ad8f1aa08a3f5d922f33d16ad0559fee339c","datavalue":{"value":{"entity-type":"item","numeric-id":750449,"id":"Q750449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$AD7B3F89-C309-4153-8DF7-75F8462D000C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d4b26c4de03cdb3a74b663694244740fe745739","datavalue":{"value":{"entity-type":"item","numeric-id":1179463,"id":"Q1179463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$DF45BFF2-6D6B-45B7-9488-8B8D508E861A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25689778c830e23fb04d27fc7257d49f1890e164","datavalue":{"value":{"entity-type":"item","numeric-id":686156,"id":"Q686156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$313D4314-D037-424F-B050-21272FC0C9E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a100fba0ec62de6bee58d0048b8aad392be6aa66","datavalue":{"value":{"entity-type":"item","numeric-id":5587729,"id":"Q5587729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$80EE3A72-9FFB-48C0-AD95-96C08817E9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7702836658cd393a9c33fb4e90fc2dd967a82b5b","datavalue":{"value":{"entity-type":"item","numeric-id":3715121,"id":"Q3715121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$25525497-64D6-4F63-BF32-9ECFD7BBA095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a8fc81c5ffde762378efab5bd1ac517be471547","datavalue":{"value":{"entity-type":"item","numeric-id":3775574,"id":"Q3775574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$04261669-02FE-459A-8369-AA538E0DF068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e8290c8d10a44b06f25c6589c811acaf2583060","datavalue":{"value":{"entity-type":"item","numeric-id":4022830,"id":"Q4022830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893175$72F96D21-B4F2-4830-8EE9-E208C0491AAF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dd084799b02d8ce25ad4380a3b2e9e46318a711","datavalue":{"value":{"entity-type":"item","numeric-id":1179463,"id":"Q1179463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9184e5008f994fbd6a64c68321435835c3d404a","datavalue":{"value":{"amount":"+0.8670555","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":"Q1893175$AAD17303-B4CC-45DE-8CA0-2A156DF2BD70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffd1f18dc539717e01cd7ccdad856bc54327b965","datavalue":{"value":{"entity-type":"item","numeric-id":3832589,"id":"Q3832589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c2fcc9132470f07c56b06eafffdd5b44bda5f03","datavalue":{"value":{"amount":"+0.82996213","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":"Q1893175$C599DF9E-2019-4DD0-98F3-58E2DCB8E660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d527d212a0afec79b22a09bfa924fa67cb49432","datavalue":{"value":{"entity-type":"item","numeric-id":750449,"id":"Q750449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89e0f3fcec18ecf52399a5b629bd837005b8b35d","datavalue":{"value":{"amount":"+0.82631636","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":"Q1893175$1F018901-0351-4FDC-8A10-E623309AF565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96cb4d0173d77bc21ec5113f4e9730ab8e0f1aaf","datavalue":{"value":{"entity-type":"item","numeric-id":2277479,"id":"Q2277479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95366c273bd6f5581d8c8b0dabe9e2931567519e","datavalue":{"value":{"amount":"+0.8196175","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":"Q1893175$A0B89F77-7AC2-44A0-8537-80EC99FDE51F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b9f4f32ccc832810d9ae7b8bf51317d66a1915b","datavalue":{"value":{"entity-type":"item","numeric-id":4010129,"id":"Q4010129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c48624724d615d0512493a5a975f54482b11bd5","datavalue":{"value":{"amount":"+0.8151552","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":"Q1893175$3F8FA5F7-4D4C-40EC-9630-BB8E76F26FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71d7e72f604f381529cffb62fb503e9f60887a70","datavalue":{"value":{"entity-type":"item","numeric-id":4327763,"id":"Q4327763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2114fdbf2e783b762e93b5a21c10ad1ed46ae15","datavalue":{"value":{"amount":"+0.80756795","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":"Q1893175$FB175FEA-1BAF-4B15-86E6-F9988FADAF6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"348d5876409baa8938e70ed57d44432159eb2a8b","datavalue":{"value":{"entity-type":"item","numeric-id":4242957,"id":"Q4242957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d30a6ac93d3f194878dbe6d92127149fabec9eb2","datavalue":{"value":{"amount":"+0.80549085","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":"Q1893175$78775DE2-E75E-4866-BB2D-17E75CD5C365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d21b886a96248a00e68af9ada1c2017300c66e6d","datavalue":{"value":{"entity-type":"item","numeric-id":2501562,"id":"Q2501562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1ca1c92ecc09187d44375fde5f39d1e2ec3f392","datavalue":{"value":{"amount":"+0.8046287","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":"Q1893175$23BB1DC6-6D5B-4847-999D-6076222CB9D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b83ac2c31c26e508752d3d4963f07023213b10a4","datavalue":{"value":{"entity-type":"item","numeric-id":4013421,"id":"Q4013421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a1f9d06a537e6727d3249f1fef1e8df21a37eae","datavalue":{"value":{"amount":"+0.8038303","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":"Q1893175$5BC7E110-1AE8-43D6-952D-C706D1C71C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f74095690caa44f21619ad25dc3d109834617753","datavalue":{"value":{"entity-type":"item","numeric-id":1322273,"id":"Q1322273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"126876cfa47f9a2e32f3d3d651bd17e6fca2b62a","datavalue":{"value":{"amount":"+0.79878294","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":"Q1893175$8FFA6DA3-DDF7-4B15-BD40-9EC3D087368D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalization of two results of Hilton on total-colourings of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalization_of_two_results_of_Hilton_on_total-colourings_of_a_graph"}}}}}