{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:11:21Z","timestamp":1725484281460},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439967"},{"type":"electronic","value":"9783540456551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45655-4_9","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T07:37:01Z","timestamp":1179733021000},"page":"67-76","source":"Crossref","is-referenced-by-count":1,"title":["Coloring Algorithms on Subcubic Graphs"],"prefix":"10.1007","author":[{"given":"Harold N.","family":"Gabow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"San","family":"Skulrattanakulchai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan (1976)","DOI":"10.1007\/978-1-349-03521-2"},{"key":"9_CR2","first-page":"25","volume":"3","author":"V.G. Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz. 3 (1964) 25\u201330 In Russian.","journal-title":"Analiz"},{"key":"9_CR3","unstructured":"Gabow, H.N., Nishizeki, T., Kariv, O., Leven, D., Terada, O.: Algorithms for edge-coloring graphs. Technical Report TRECIS-8501, Tohoku University (1985)"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I.J. Holyer","year":"1981","unstructured":"Holyer, I.J.: The NP-completeness of edge-coloring. SIAM Journal on Computing 10 (1981) 718\u2013720","journal-title":"SIAM Journal on Computing"},{"key":"9_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Gary","year":"1979","unstructured":"Gary, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., San Francisco, CA (1979)"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0020-0190(01)00221-6","volume":"81","author":"S. Skulrattanakulchai","year":"2002","unstructured":"Skulrattanakulchai, S.: 4-edge-coloring graphs of maximum degree 3 in linear time. Information Processing Letters 81 (2002) 191\u2013195","journal-title":"Information Processing Letters"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF02582936","volume":"1","author":"B. Bollob\u00e1s","year":"1985","unstructured":"Bollob\u00e1s, B., Harris, A.J.: List-colourings of graphs. Graphs and Combinatorics 1 (1985) 115\u2013127","journal-title":"Graphs and Combinatorics"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1002\/jgt.3190130112","volume":"13","author":"A.G. Chetwynd","year":"1989","unstructured":"Chetwynd, A.G., H\u00e4ggkvist, R.: A note on list-colorings. Journal of Graph Theory 13 (1989) 87\u201395","journal-title":"Journal of Graph Theory"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. John Wiley & Sons (1995)","DOI":"10.1002\/9781118032497"},{"key":"9_CR10","first-page":"3","volume":"29","author":"V.G. Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. Metody Diskret. Anal. v Teorii Kodov i Schem 29 (1976) 3\u201310","journal-title":"Metody Diskret. Anal. v Teorii Kodov i Schem"},{"key":"9_CR11","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings of the West-Coast Conference on Combinatorics, Graph Theory and Computing. Volume XXVI of Congressus Numerantium., Arcata, California (1979) 125\u2013157"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Proceedings of the Cambridge Philosophical Society. Mathematical and Physical Sciences 37 (1941) 194\u2013197","DOI":"10.1017\/S030500410002168X"},{"key":"9_CR13","series-title":"Lect Notes Comput Sci","volume-title":"Proc. SWAT\u2019 02","author":"S. Skulrattanakulchai","year":"2002","unstructured":"Skulrattanakulchai, S.: \u0394-list vertex coloring in linear time. In: Proc. SWAT\u2019 02. LNCS (2002) To appear."},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0012-365X(97)00230-6","volume":"187","author":"M. Juvan","year":"1998","unstructured":"Juvan, M., Mohar, B., \u0160krekovski, R.: On list edge-colorings of subcubic graphs. Discrete Mathematics 187 (1998) 137\u2013149","journal-title":"Discrete Mathematics"},{"key":"9_CR15","unstructured":"S\u00e1nchez-Arroyo, A.: Total colourings and complexity. Master\u2019s thesis, University of Oxford (1989)"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0012-365X(89)90187-8","volume":"78","author":"A. S\u00e1nchez-Arroyo","year":"1989","unstructured":"S\u00e1nchez-Arroyo, A.: Determining the total colouring number is NP-hard. Discrete Mathematics 78 (1989) 315\u2013319","journal-title":"Discrete Mathematics"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Yap, H.P.: Total Colourings of Graphs. LNM Volume 1623. Springer (1996)","DOI":"10.1007\/BFb0092895"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BF02771690","volume":"9","author":"M. Rosenfeld","year":"1971","unstructured":"Rosenfeld, M.: On the total coloring of certain graphs. Israel Journal of Mathematics 9 (1971) 396\u2013402","journal-title":"Israel Journal of Mathematics"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1112\/jlms\/s2-3.3.405","volume":"3","author":"N. Vijayaditya","year":"1971","unstructured":"Vijayaditya, N.: On total chromatic number of a graph. Journal of the London Mathematical Society 3 (1971) 405\u2013408","journal-title":"Journal of the London Mathematical Society"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jagm.2000.1132","volume":"38","author":"T.C. Biedl","year":"2001","unstructured":"Biedl, T.C., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen\u2019s Matching Theorem. Journal of Algorithms 38 (2001) 110\u2013134","journal-title":"Journal of Algorithms"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1017\/S0963548397003210","volume":"7","author":"M. Juvan","year":"1998","unstructured":"Juvan, M., Mohar, B., \u0160krekovski, R.: List total colorings of graphs. Combinatorics, Probability & Computing 7 (1998) 181\u2013188","journal-title":"Combinatorics, Probability & Computing"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1006\/jctb.1997.1780","volume":"71","author":"O.V. Borodin","year":"1997","unstructured":"Borodin, O.V., Kostochka, A.V., Woodall, D.R.: List edge and list total colourings of multigraphs. Journal of Combinatorial Theory Series B 71 (1997) 184\u2013204","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"9_CR23","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. Second edn. McGraw-Hill, New York (2001)","edition":"Second edn."},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2000.1146","volume":"39","author":"S. Halperin","year":"2001","unstructured":"Halperin, S., Zwick, U.: Optimal randomized EREW PRAM algorithms for finding spanning forests. Journal of Algorithms 39 (2001) 1\u201346","journal-title":"Journal of Algorithms"},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM Journal on Computing 14 (1985) 862\u2013874","journal-title":"SIAM Journal on Computing"},{"volume-title":"Synthesis of Parallel Algorithms","year":"1993","key":"9_CR26","unstructured":"Reif, J.H., ed.: Synthesis of Parallel Algorithms. Morgan Kaufmann, CA (1993)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45655-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T02:27:22Z","timestamp":1556418442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45655-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439967","9783540456551"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45655-4_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}