{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:46Z","timestamp":1725603646792},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_67","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"799-810","source":"Crossref","is-referenced-by-count":0,"title":["Cover-Decomposition and Polychromatic Numbers"],"prefix":"10.1007","author":[{"given":"B\u00e9la","family":"Bollob\u00e1s","sequence":"first","affiliation":[]},{"given":"David","family":"Pritchard","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"67_CR1","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/BFb0070378","volume-title":"Theory and Applications of Graphs: Int. Conf. Kalamazoo","author":"R.P. Gupta","year":"1976","unstructured":"Gupta, R.P.: On the chromatic index and the cover index of a mulltigraph. In: Alavi, Y., Lick, D.R. (eds.) Theory and Applications of Graphs: Int. Conf. Kalamazoo, May 11-15. Lecture Notes in Mathematics, vol.\u00a0642, pp. 204\u2013215. Springer, Heidelberg (1976)"},{"key":"67_CR2","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0012-365X(79)90076-1","volume":"25","author":"L.D. Andersen","year":"1979","unstructured":"Andersen, L.D.: Lower bounds on the cover-index of a graph. Discrete Mathematics\u00a025, 199\u2013210 (1979)","journal-title":"Discrete Mathematics"},{"key":"#cr-split#-67_CR3.1","doi-asserted-by":"crossref","unstructured":"Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B., Zumstein, P.: Polychromatic colorings of plane graphs. Discrete & Computational Geometry\u00a042(3), 421\u2013442 (2009);","DOI":"10.1007\/s00454-009-9171-5"},{"key":"#cr-split#-67_CR3.2","unstructured":"Preliminary version appeared in Proc. 24th SOCG, pp. 338\u2013345 (2008)"},{"key":"67_CR4","unstructured":"P\u00e1lv\u00f6lgyi, D.: Decomposition of Geometric Set Systems and Graphs. PhD thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, arXiv:1009.4641 (2010)"},{"key":"67_CR5","unstructured":"Elekes, M., M\u00e1trai, T., Soukup, L.: On splitting infinite-fold covers. Fund. Math. 212, 95\u2013127 (2011); arXiv:0911.2774"},{"key":"67_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-93980-1_1","volume-title":"Approximation and Online Algorithms","author":"J. K\u00f6nemann","year":"2009","unstructured":"K\u00f6nemann, J., Parekh, O., Pritchard, D.: Max-weight integral multicommodity flow in spiders and high-capacity trees. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol.\u00a05426, pp. 1\u201314. Springer, Heidelberg (2009)"},{"key":"#cr-split#-67_CR7.1","doi-asserted-by":"crossref","unstructured":"Pach, J., Tardos, G., T\u00f3th, G.: Indecomposable coverings. Canadian Mathematical Bulletin 52, 451-463 (2009);","DOI":"10.4153\/CMB-2009-048-x"},{"key":"#cr-split#-67_CR7.2","unstructured":"Preliminary version in Proc. 7th CJCDGCGT (2005), pp. 135-148 (2007)"},{"key":"#cr-split#-67_CR8.1","doi-asserted-by":"crossref","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz Local Lemma. J. ACM 57 (2010);","DOI":"10.1145\/1667053.1667060"},{"key":"#cr-split#-67_CR8.2","unstructured":"Preliminary version in Proc.\u00a041st STOC, pp. 343\u2013350 (2009)"},{"key":"67_CR9","unstructured":"Buchsbaum, A.L., Efrat, A., Jain, S., Venkatasubramanian, S., Yi, K.: Restricted strip covering and the sensor cover problem. In: Proc. 18th SODA, pp. 1056\u20131063 (2007)"},{"key":"67_CR10","doi-asserted-by":"crossref","unstructured":"Gibson, M., Varadarajan, K.: Decomposing coverings and the planar sensor cover problem. In: Proc.\u00a050th FOCS, pp. 159\u2013168 (2009)","DOI":"10.1109\/FOCS.2009.54"},{"key":"67_CR11","unstructured":"Pach, J., Tardos, G.: Tight lower bounds for the size of epsilon-nets. In: Proc 27th SoCG, pp. 458\u2013463 (2011) arXiv:1012.1240"},{"key":"#cr-split#-67_CR12.1","doi-asserted-by":"crossref","unstructured":"Feige, U., Halld\u00f3rsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput.\u00a032, 172\u2013195 (2002);","DOI":"10.1137\/S0097539700380754"},{"key":"#cr-split#-67_CR12.2","unstructured":"Preliminary version appeared in Proc. 32nd STOC, pp. 134\u2013143 (2000)"},{"key":"67_CR13","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1002\/rsa.20274","volume":"35","author":"G. C\u0103linescu","year":"2009","unstructured":"C\u0103linescu, G., Chekuri, C., Vondr\u00e1k, J.: Disjoint bases in a polymatroid. Random Struct. Algorithms\u00a035, 418\u2013430 (2009)","journal-title":"Random Struct. Algorithms"},{"key":"67_CR14","unstructured":"Pach, J.: Decomposition of multiple packing and covering. In: Kolloquium \u00fcber Diskrete Geometrie, Salzburg, Inst.\u00a0Math.\u00a0U.\u00a0Salzburg, pp. 169\u2013178 (1980)"},{"key":"67_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-12200-2_2","volume-title":"LATIN 2010: Theoretical Informatics","author":"G. Aloupis","year":"2010","unstructured":"Aloupis, G., Cardinal, J., Collette, S., Imahori, S., Korman, M., Langerman, S., Schwartz, O., Smorodinsky, S., Taslakian, P.: Colorful strips. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 2\u201313. Springer, Heidelberg (2010)"},{"key":"67_CR16","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Octants are cover decomposable (2011); arXiv:1101.3773"},{"key":"#cr-split#-67_CR17.1","unstructured":"Keszegh, B.: Weak conflict free colorings of point sets and simple regions. In: Proc. 19th CCCG (2007);"},{"key":"#cr-split#-67_CR17.2","unstructured":"Extended version \u201cColoring half-planes and bottomless rectangles\u201d at arXiv:1105.0169"},{"key":"67_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1007\/3-540-48481-7_44","volume-title":"Algorithms - ESA\u201999","author":"J. Cheriyan","year":"1999","unstructured":"Cheriyan, J., Jord\u00e1n, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol.\u00a01643, pp. 510\u2013520. Springer, Heidelberg (1999)"},{"key":"67_CR19","unstructured":"Cheilaris, P., Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Unique-maximum and conflict-free colorings for hypergraphs and tree graphs. In: Proc.\u00a07th Japanese-Hungarian Symp.\u00a0Disc.\u00a0Math.\u00a0Appl., pp. 207\u2013216 (2011); arXiv:1002.4210"},{"key":"#cr-split#-67_CR20.1","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Jansen, K.: The maximum edge-disjoint paths problem in bidirected trees. SIAM J. Discrete Math.\u00a014, 326\u2013355 (2001);","DOI":"10.1137\/S0895480199361259"},{"key":"#cr-split#-67_CR20.2","unstructured":"Preliminary version in Proc.\u00a09th ISAAC (1998)"},{"key":"67_CR21","series-title":"Colloq. Math. Soc. J\u00e1nos Bolyai","first-page":"609","volume-title":"Infinite and Finite Sets (Coll.\u00a0Keszthely, 1973)","author":"P. Erd\u0151s","year":"1975","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hajnal, A., Rado, R., S\u00f3s, V.T. (eds.) Infinite and Finite Sets (Coll.\u00a0Keszthely, 1973). Colloq. Math. Soc. J\u00e1nos Bolyai, vol.\u00a010, pp. 609\u2013627. North-Holland, Amsterdam (1975)"},{"key":"67_CR22","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, New York (2008)","edition":"3"},{"key":"67_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J. Beck","year":"1981","unstructured":"Beck, J., Fiala, T.: \u201cInteger-making\u201d theorems. Discrete Applied Mathematics\u00a03, 1\u20138 (1981)","journal-title":"Discrete Applied Mathematics"},{"key":"67_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1090\/S0894-0347-1992-1135027-1","volume":"5","author":"C. Thomassen","year":"1992","unstructured":"Thomassen, C.: The even cycle problem for directed graphs. J. Amer. Math. Soc.\u00a05, 217\u2013229 (1992)","journal-title":"J. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_67","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T15:50:57Z","timestamp":1554133857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}