{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:16:51Z","timestamp":1758824211876},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1986,3,1]],"date-time":"1986-03-01T00:00:00Z","timestamp":510019200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,3]]},"DOI":"10.1007\/bf02579408","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T18:19:26Z","timestamp":1174587566000},"page":"49-54","source":"Crossref","is-referenced-by-count":20,"title":["Legal coloring of graphs"],"prefix":"10.1007","volume":"6","author":[{"given":"N.","family":"Linial","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02579408_CR1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"D. P. Dobkin","year":"1979","unstructured":"D. P. Dobkin andR. J. Lipton, On the complexity of computations under varying sets of primitives,J. Computer and System Science,18 (1979), 86\u201391.","journal-title":"J. Computer and System Science"},{"key":"BF02579408_CR2","doi-asserted-by":"crossref","unstructured":"C. Greene, Acyclic orientations (Notes),in: Higher Combinatorics (M. Aigner, ed.), pp. D. Reidel, Dordrecht, 1977, 65\u201368.","DOI":"10.1007\/978-94-010-1220-1_4"},{"key":"BF02579408_CR3","volume-title":"Convex Polytopes","author":"B. Gr\u00fcnbaum","year":"1967","unstructured":"B. Gr\u00fcnbaum,Convex Polytopes, Interscience, New York, 1967."},{"key":"BF02579408_CR4","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/322203.322206","volume":"27","author":"R. L. Graham","year":"1980","unstructured":"R. L. Graham, A. C. Yao andF. F. Yao, Information bounds are weak in the shortest distance problem,J. Assoc. Comp. Mach.,27 (1980), 428\u2013444.","journal-title":"J. Assoc. Comp. Mach."},{"key":"BF02579408_CR5","doi-asserted-by":"crossref","unstructured":"U. Manber andM. Tompa, The effect of number of Hamiltonian paths on the complexity of a vertex coloring problem.Proc. 22nd Annual Symposium on the Foundations of Computer Science, 1981.","DOI":"10.1109\/SFCS.1981.47"},{"key":"BF02579408_CR6","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1137\/0209028","volume":"9","author":"R. Rivest","year":"1980","unstructured":"R. Rivest andA. C. Yao, On the polyhedral decision problem,SIAM J. Computing,9 (1980), 343\u2013347.","journal-title":"SIAM J. Computing"},{"key":"BF02579408_CR7","doi-asserted-by":"crossref","unstructured":"M. Snir, Proving lower bounds for linear decision trees,in: Proc. 8th. International Coll. on Automata Languages and Programming, Lecture Notes in Computer Science 115, Springer Verlag, (1981), 305\u2013315.","DOI":"10.1007\/3-540-10843-2_25"},{"key":"BF02579408_CR8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"R. P. Stanley","year":"1973","unstructured":"R. P. Stanley, Acyclic orientations of graphs,Discrete Math.,5 (1973), 171\u2013178.","journal-title":"Discrete Math."},{"key":"BF02579408_CR9","volume-title":"Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes, Mem. AMS.","author":"T. Zaslavsky","year":"1975","unstructured":"T. Zaslavsky,Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes, Mem. AMS. 154, Amer. Math. Soc., Providence, R. I., 1975."},{"key":"BF02579408_CR10","doi-asserted-by":"crossref","unstructured":"T. Zaslavsky, The geometry of root systems and signed graphs,Amer. Math. Monthly (1981), 88\u2013105.","DOI":"10.1080\/00029890.1981.11995201"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579408.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579408\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T12:45:04Z","timestamp":1558183504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,3]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1986,3]]}},"alternative-id":["BF02579408"],"URL":"https:\/\/doi.org\/10.1007\/bf02579408","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,3]]}}}