{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T18:59:01Z","timestamp":1778871541658,"version":"3.51.4"},"reference-count":39,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2004,2]]},"abstract":"<jats:p>We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n\/ log n) processors and runs in O( log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.<\/jats:p>","DOI":"10.1142\/s0129054104002285","type":"journal-article","created":{"date-parts":[[2004,3,18]],"date-time":"2004-03-18T12:03:47Z","timestamp":1079611427000},"page":"21-40","source":"Crossref","is-referenced-by-count":3,"title":["COLORING ALGORITHMS ON SUBCUBIC GRAPHS"],"prefix":"10.1142","volume":"15","author":[{"given":"SAN","family":"SKULRATTANAKULCHAI","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Colorado at Boulder, Boulder CO 80309-0430, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HAROLD N.","family":"GABOW","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Colorado at Boulder, Boulder CO 80309-0430, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"rf2","volume-title":"Technical Report CS-2000-17","author":"Biedl Therese C.","year":"2000"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1132"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582936"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1780"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130112"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261320"},{"key":"rf12","volume-title":"Technical Report TRECIS-8501","author":"Gabow Harold N.","year":"1985"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45655-4_9"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1011"},{"key":"rf15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Gary Michael R.","year":"1979"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1145\/234782.234783"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1146"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"rf19","volume-title":"Graph Coloring Problems","author":"Jensen Tommy R.","year":"1995"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003210"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00230-6"},{"key":"rf23","doi-asserted-by":"crossref","first-page":"R42","DOI":"10.37236\/1474","volume":"6","author":"Juvan Martin","journal-title":"The Electronic Journal of Combinatorics"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90246-E"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10029"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10030"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90089-1"},{"key":"rf29","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)00058-Y"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00293-3"},{"key":"rf32","volume-title":"Synthesis of Parallel Algorithms","author":"Reif John H.","year":"1993"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771690"},{"key":"rf34","volume-title":"The Four-Color Problem, Assaults and Conquest","author":"Saaty Thomas L.","year":"1986"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90187-8"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00221-6"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45471-3_25"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"rf41","first-page":"405","volume":"3","author":"Vijayaditya N.","journal-title":"Journal of the London Mathematical Society"},{"key":"rf42","first-page":"25","volume":"3","author":"Vizing Vadim G.","journal-title":"Metody Diskret. Analiz."},{"key":"rf43","first-page":"3","volume":"29","author":"Vizing Vadim G.","journal-title":"Metody Diskret. Anal. v Teorii Kodov i Schem"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00297-0"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0092895"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054104002285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T17:23:45Z","timestamp":1585675425000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054104002285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,2]]},"references-count":39,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,2]]}},"alternative-id":["10.1142\/S0129054104002285"],"URL":"https:\/\/doi.org\/10.1142\/s0129054104002285","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,2]]}}}