{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1124604","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1124604","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1124604","kernelVersion":"v1","immutable":true,"modified":"2026-01-06T22:36:49Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1124604","name":"Clique partitions and clique coverings","headline":"Clique partitions and clique coverings","description":"scientific article; zbMATH DE number 4112628","url":"https://portal.mardi4nfdi.de/entity/Q1124604","datePublished":"1988-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1124603"},{"@id":"https://portal.mardi4nfdi.de/entity/Q175582"},{"@id":"https://portal.mardi4nfdi.de/entity/Q6480801"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q175483"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0012-365X(88)90197-5","url":"https://doi.org/10.1016/0012-365X(88)90197-5"},"sameAs":["https://doi.org/10.1016/0012-365X(88)90197-5"],"comment":"Only undirected graphs without loops or multiple edges are considered here. \\(K_n\\) is a clique on \\(n\\) vertices. The clique covering number and the clique partition number of the graph \\(G\\) is denoted by \\(cc(G)\\) and \\(cp(G)\\)respectively. The authors obtain asymptotic results for \\(cp(K_n-K_m)\\) for m in the range \\(\\sqrt{n}<m<n\\); for example if \\(m=cn^a\\), \\(1/2<a<1\\), then \\(cp(K_n-K_m)\\) is asymptotic to \\(c^2n^{2a}\\). They apply bounds developed in this connection to bound the maximum value of \\(cp(G)/cc(G)\\) on graphs G with n vertices, showing it can grow as fast as \\(cn^2\\) where \\(c>1/64\\). Further they prove that if \\(T_n\\) is \\(K_n\\) minus a matching then, for all \\(n\\), \\((\\log n)-1\\leq cc(T_n)\\leq 2(\\log n).\\)","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3691766"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5512009"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1076691"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1164073"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4152571"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3922720"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1167740"}]},"provenance":{"prov:generatedAtTime":"2026-01-06T22:36:49Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}