{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T21:57:47Z","timestamp":1761861467491},"reference-count":44,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,7,1]],"date-time":"2001-07-01T00:00:00Z","timestamp":993945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4399,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,7]]},"DOI":"10.1016\/s0304-3975(00)00231-0","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"59-74","source":"Crossref","is-referenced-by-count":10,"title":["Graph colourings and partitions"],"prefix":"10.1016","volume":"263","author":[{"given":"V.","family":"Yegnanarayanan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(00)00231-0_BIB1","doi-asserted-by":"crossref","first-page":"159","DOI":"10.4064\/fm-102-3-159-164","article-title":"On the pseudoachromatic number of a graph","volume":"102","author":"Bhave","year":"1979","journal-title":"Fund. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB2","first-page":"323","article-title":"On the application of the properties of Galois fields to the problem of construction of hyper-Graceo-Latin squares, Sankhya, Indian","volume":"3","author":"Bose","year":"1938","journal-title":"J. Statist."},{"issue":"3-4","key":"10.1016\/S0304-3975(00)00231-0_BIB3","first-page":"331","article-title":"Indice achromatique des graphes multiparti complets et reguliers","volume":"20","author":"Bouchet","year":"1978","journal-title":"Cahiers centre Etudes Rech. Oper."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB4","doi-asserted-by":"crossref","first-page":"88","DOI":"10.4153\/CJM-1949-009-2","article-title":"The non-existence of certain finite projective planes","volume":"1","author":"Bruck","year":"1949","journal-title":"Can. J. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB5","first-page":"55","article-title":"Graphical theorems of the Nordhaus\u2013Gaddum class","volume":"vol. 186","author":"Chartrand","year":"1971"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB6","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB7","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(85)90039-5","article-title":"Colouring the real line","volume":"39","author":"Eggleton","year":"1985","journal-title":"J. Combin. Theory (B)"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB8","first-page":"323","article-title":"Research problem 77","volume":"58","author":"Eggleton","year":"1986","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB9","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01787476","article-title":"Colouring prime distance graphs","volume":"32","author":"Eggleton","year":"1990","journal-title":"Graphs Combin."},{"issue":"101","key":"10.1016\/S0304-3975(00)00231-0_BIB10","doi-asserted-by":"crossref","first-page":"283","DOI":"10.21136\/CMJ.1976.101401","article-title":"Distance in graphs","volume":"26","author":"Entringer","year":"1976","journal-title":"Czechoslovak Math. J."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0095-8956(86)90062-6","article-title":"Concerning the achromatic number of graphs","volume":"40","author":"Farber","year":"1986","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB12","unstructured":"H.J. Fink, On the chromatic numbers of a graph and its complement, in: P. Erdos, G. Katona (Eds.), Theory of Graphs (Proceedings of the Coll. Tihany, 1966) Akademiai, Kiado, Budapest, 1968, pp. 99\u2013113."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB13","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02066678","article-title":"Maximum\u2013Minimum Satze und verallemeinerte Faktoren von Graphen","volume":"12","author":"Gallai","year":"1961","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB14","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB15","doi-asserted-by":"crossref","first-page":"285","DOI":"10.4064\/fm-85-3-285-290","article-title":"Further results on the achromatic number","volume":"85","author":"Geller","year":"1974","journal-title":"Fund. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB16","series-title":"Proceedings of the Third Conference on Combinatorics, Waterloo, 1968,","first-page":"229","article-title":"Bounds on the chromatic and achromatic numbers of complementary graphs in recent trends in combinatorics","author":"Gupta","year":"1969"},{"issue":"3","key":"10.1016\/S0304-3975(00)00231-0_BIB17","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1137\/0110037","article-title":"On realizability of a set of integers as degrees of the vertices of a linear graph","volume":"10","author":"Hakimi","year":"1962","journal-title":"J. Soc. Indust. Appl. Math. USA"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB18","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1090\/S0002-9947-1943-0008892-4","article-title":"Projective planes","volume":"54","author":"Hall","year":"1943","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB19","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/S0021-9800(70)80072-2","article-title":"The achromatic number of a graph","volume":"8","author":"Harary","year":"1970","journal-title":"J. Combin. Theory"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB20","first-page":"453","article-title":"An interpolation theorem for graphical homomorphisms","volume":"26","author":"Harary","year":"1967","journal-title":"Portugal. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB21","first-page":"332","article-title":"Map colour theorems","volume":"24","author":"Heawood","year":"1890","journal-title":"Quart. J. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB22","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0012-365X(89)90202-1","article-title":"On the edge achromatic numbers of complete graphs","volume":"23","author":"Jamison","year":"1989","journal-title":"Discrete. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB23","series-title":"Reducibility Among Combinatorial Problems, Complexity of Computer Computations","first-page":"85","author":"Karp","year":"1972"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB24","doi-asserted-by":"crossref","first-page":"193","DOI":"10.2307\/2369235","article-title":"On the geographical problem of four colours","volume":"2","author":"Kempe","year":"1879","journal-title":"Amer. J. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB25","series-title":"Finite Geometrical Systems","author":"Levi","year":"1942"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB26","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1090\/S0002-9904-1944-08127-5","article-title":"Orthogonal Latin squares","volume":"50","author":"Mann","year":"1944","journal-title":"Bull. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB27","doi-asserted-by":"crossref","first-page":"175","DOI":"10.2307\/2306658","article-title":"On complementary graphs","volume":"63","author":"Nordhaus","year":"1956","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB28","doi-asserted-by":"crossref","unstructured":"J. Pach, R. Pollack, J. Spencer, Graph distance and Euclidean distance on the grid, in: B. Rainer, H. Ruddf (Eds.), Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg, 1990.","DOI":"10.1007\/978-3-642-46908-4_63"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB29","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.3190080102","article-title":"On the sum of all distances in a graph or digraph","volume":"8","author":"Plesnick","year":"1984","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB31","doi-asserted-by":"crossref","unstructured":"K. Schnabel, Representation of graphs by integers, in: B. Rainer, H. Ruddf (Eds.), Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg.","DOI":"10.1007\/978-3-642-46908-4_73"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB32","series-title":"Problems in Combinatorics and Graph Theory","author":"Tomescu","year":"1985"},{"issue":"2","key":"10.1016\/S0304-3975(00)00231-0_BIB33","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1093\/qmath\/40.4.475","article-title":"On distances in chromatic graphs","volume":"40","author":"Tomescu","year":"1989","journal-title":"Quart. J. Math. Oxford"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB34","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1090\/S0002-9947-1906-1500747-6","article-title":"Finite projective geometries","volume":"7","author":"Veblen","year":"1906","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB35","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1090\/S0002-9947-1907-1500792-1","article-title":"Non-desarguesian and non Pascalian geometries","volume":"8","author":"Veblen","year":"1907","journal-title":"Trans. Amer. Math. Soc."},{"issue":"3","key":"10.1016\/S0304-3975(00)00231-0_BIB36","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","article-title":"Edge dominating sets in graphs","volume":"38","author":"Yannakakis","year":"1980","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB37","series-title":"On graph colourings and labellings, Doctoral Thesis","author":"Yegnanarayanan","year":"1996"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB38","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0012-365X(97)00216-1","article-title":"Extremal graphs in some colouring problems","volume":"186","author":"Yegnanarayanan","year":"1998","journal-title":"Discrete Math."},{"issue":"1\u20132","key":"10.1016\/S0304-3975(00)00231-0_BIB39","first-page":"23","article-title":"Concerning psuedocomplete partitioning of graphs","volume":"XLVIII","author":"Yegnanarayanan","year":"1998","journal-title":"Pure Appl. Math. Sci."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB40","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s10012-000-0129-z","article-title":"The psuedoachromatic number of a graph","volume":"24","author":"Yegnanarayanan","year":"2000","journal-title":"Southeast Asian Bulletin of Mathematics"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB41","first-page":"147","article-title":"An existence result of Nordhaus\u2013Gaddum class, Bulletin of the Allahabad Mathematical Society","volume":"14","author":"Yegnanarayanan","year":"1999","journal-title":"B.N. Prasad"},{"key":"10.1016\/S0304-3975(00)00231-0_BIB42","unstructured":"V. Yegnanarayanan, On some extremal graph problems of the Nordhaus\u2013Gaddum class, submitted for publication."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB43","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0012-365X(99)00351-9","article-title":"A note on the existence of graphs with prescribed colouring parameters","volume":"216","author":"Yegnanarayanan","year":"2000","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(00)00231-0_BIB44","first-page":"163","article-title":"On some properties of linear complexes","volume":"24","author":"Zykov","year":"1949","journal-title":"Math. Sb."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500002310?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500002310?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T22:04:55Z","timestamp":1620165895000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500002310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,7]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,7]]}},"alternative-id":["S0304397500002310"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00231-0","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,7]]}}}