{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T01:45:42Z","timestamp":1764812742732},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_12","type":"book-chapter","created":{"date-parts":[[2010,9,3]],"date-time":"2010-09-03T21:16:57Z","timestamp":1283548617000},"page":"131-142","source":"Crossref","is-referenced-by-count":6,"title":["Backbone Colorings for Networks"],"prefix":"10.1007","author":[{"given":"Hajo","family":"Broersma","sequence":"first","affiliation":[]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"Agnarsson, G., Halld\u00f3rsson, M.M.: Coloring powers of planar graphs. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pp. 654\u2013662 (2000)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/3-540-46541-3_33","volume-title":"STACS 2000","author":"H.L. Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: \u03bb-coloring of graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 395\u2013406. Springer, Heidelberg (2000)"},{"key":"12_CR3","unstructured":"Borodin, O.V., Broersma, H.J., Glebov, A., van den Heuvel, J.: Stars and bunches in planar graphs. Part I: Triangulations (2001) (preprint)"},{"key":"12_CR4","unstructured":"Borodin, O.V., Broersma, H.J., Glebov, A., van den Heuvel, J.: Stars and bunches in planar graphs. Part II: General planar graphs and colourings (2001) (preprint)"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/S0895480193245339","volume":"9","author":"G.J. Chang","year":"1996","unstructured":"Chang, G.J., Kuo, D.: The L(2,1)-labeling problem on graphs. SIAM J. Discrete Math.\u00a09, 309\u2013316 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/3-540-44676-1_39","volume-title":"Algorithms - ESA 2001","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Fishkin, A.V., Fomin, F.V.: Off-line and on-line distance constrained labeling of graphs. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 464\u2013475. Springer, Heidelberg (2001)"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kloks, T., Kratochv\u00edl, J.: Fixed-parameter complexity of \u03bb- labelings. Discrete Appl. Math.\u00a0113, 59\u201372 (2001)","journal-title":"Discrete Appl. Math."},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/3-540-45446-2_18","volume-title":"Theoretical Computer Science","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kratochv\u00edl, J., Proskurowski, A.: Distance constrained labelings of precolored trees. In: Restivo, A., Ronchi Della Rocca, S., Roversi, L. (eds.) ICTCS 2001. LNCS, vol.\u00a02202, pp. 285\u2013292. Springer, Heidelberg (2001)"},{"key":"12_CR9","first-page":"152","volume":"75","author":"D.A. Fotakis","year":"2001","unstructured":"Fotakis, D.A., Nikoletseas, S.E., Papadopoulou, V.G., Spirakis, P.G.: Hardness results and efficient approximations for frequency assignment problems and the radio coloring problem. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS\u00a075, 152\u2013180 (2001)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"12_CR10","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"12_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"J.R. Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math.\u00a05, 586\u2013595 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"W.K. Hale","year":"1980","unstructured":"Hale, W.K.: Frequency assignment: Theory and applications. Proceedings of the IEEE\u00a068, 1497\u20131514 (1980)","journal-title":"Proceedings of the IEEE"},{"key":"12_CR14","first-page":"311","volume":"19","author":"P.L. Hammer","year":"1977","unstructured":"Hammer, P.L., F\u00f6ldes, S.: Split graphs. Congressus Numerantium\u00a019, 311\u2013315 (1977)","journal-title":"Congressus Numerantium"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V","volume":"29","author":"J. Heuvel van den","year":"1998","unstructured":"van den Heuvel, J., Leese, R.A., Shepherd, M.A.: Graph labeling and radio channel assignment. J. Graph Theory\u00a029, 263\u2013283 (1998)","journal-title":"J. Graph Theory"},{"key":"12_CR16","unstructured":"van den Heuvel, J., McGuinness, S.: Colouring the square of a planar graph (1999) (preprint)"},{"key":"12_CR17","unstructured":"Jonas, T.K.: Graph coloring analogues with a condition at distance two: L(2,1)-labellings and list \u03bb-labellings. Ph.D. Thesis, University of South Carolina (1993)"},{"key":"12_CR18","unstructured":"Leese, R.A.: Radio spectrum: a raw material for the telecommunications industry. In: Progress in Industrial Mathematics at ECMI 1998, Teubner, Stuttgart, pp. 382\u2013396 (1999)"},{"key":"12_CR19","unstructured":"Molloy, M., Salavatipour, M.R.: A bound on the chromatic number of the square of a planar graph (2001) (preprint)"},{"key":"12_CR20","unstructured":"Wegner, G.: Graphs with given diameter and a colouring problem. University of Dortmund (1977) (preprint)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T18:14:13Z","timestamp":1553019253000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}