@string{accept = {Accepted for publication}} @string{accs = { Automatic Control and Computer Sciences}} @string{acm = {The Association for Computing Machinery}} @string{acp = {The Art of Computer Programming}} @string{actac = {Acta Cybernetica}} @string{adm = {Annals of Discrete Mathematics}} @string{advmath = {Advances in Mathematics}} @string{ae = {American Elsevier Publishing Company, Inc.}} @string{aea = {New York, New York}} @string{ai = {Artificial Intelligence}} @string{algo = {Algorithmica}} @string{aller = {Proceedings of the Allerton Conference on Communication, Control and Computing}} @string{allerp = {Allerton Press, Inc.}} @string{allerpa = {New York, New York}} @string{am = {Aequationes Mathematicae}} @string{aml = {Annals of Mathematical Logic}} @string{amm = {The American Mathematical Monthly}} @string{amscp = {American Mathematical Society Colloquium Publications}} @string{aor = {Annals of Operations Research}} @string{ap = {Academic Press, Inc.}} @string{apa = {Orlando, Florida}} @string{apal = {Annals of Pure and Applied Logic}} @string{arsco = {Ars Combinatoria}} @string{aster = {Ast\'erisque}} @string{atlas = {Proceedings of the Atlas Conference}} @string{atlas71 = {Proceedings of the 2nd Atlas Conference}} @string{atlas71v = {2}} @string{aw = {Addison-Wesley Publishing Company, Inc.}} @string{awa = {Reading, Massachusetts}} @string{bams = {Bulletin of the American Mathematical Society}} @string{beatcs = {Bulletin of the EATCS}} @string{bit = {BIT}} @string{ccero = { Cahiers du Centre d'Etudes de Recherche Operationnelle}} @string{cgip = {Computer Graphics and Image Processing}} @string{ch = {Chapman and Hall, Ltd.}} @string{cha = {London, UK}} @string{cjc = { Chinese Journal of Computers}} @string{cjm = {Canadian Journal of Mathematics}} @string{cmpmth = { Computers and Mathematics with Applications}} @string{cmsjb = {Colloquia Mathematica Societatis J\'anos Bolyai}} @string{comb = {Combinatorica}} @string{comp = {Computing}} @string{connum = {Congressus Numerantium}} @string{cor = {Computers and Operations Research}} @string{csp = {Computer Science Press, Inc.}} @string{cspa = {Rockville, Maryland}} @string{cyb = {Cybernetics}} @string{cybsys = {Cybernetics and Systems}} @string{dam = {Discrete Applied Mathematics}} @string{dcg = {Discrete and Computational Geometry}} @string{depeecs = {Department of Electrical Engineering and Computer Science}} @string{dimacs = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science}} @string{dm = {Discrete Mathematics}} @string{dux = {Duxbury Press}} @string{duxa = {Boston, Massachusetts}} @string{eatcs = {European Association for Theoretical Computer Science}} @string{edm = {Elemente der Mathematik}} @string{ejc = {European Journal of Combinatorics}} @string{ejor = {European Journal of Operational Research}} @string{ensm = {L'Enseignement Math\'ematique}} @string{fall = {Fall}} @string{focs = {Annual Symposium on Foundations of Computer Science}} @string{focs78 = {19th Annual Symposium on Foundations of Computer Science}} @string{focs78v = {19}} @string{focs79 = {20th Annual Symposium on Foundations of Computer Science}} @string{focs79v = {20}} @string{focs80 = {21st Annual Symposium on Foundations of Computer Science}} @string{focs80v = {21}} @string{focs81 = {22nd Annual Symposium on Foundations of Computer Science}} @string{focs81a = {Nashville, Tennessee}} @string{focs81v = {22}} @string{focs82 = {23rd Annual Symposium on Foundations of Computer Science}} @string{focs82a = {Chicago, Illinois}} @string{focs82v = {23}} @string{focs83 = {24th Annual Symposium on Foundations of Computer Science}} @string{focs83a = {Tucson, Arizona}} @string{focs83v = {24}} @string{focs84 = {25th Annual Symposium on Foundations of Computer Science}} @string{focs84a = {Singer Island, Florida}} @string{focs84v = {25}} @string{focs85 = {26th Annual Symposium on Foundations of Computer Science}} @string{focs85a = {Portland, Oregon}} @string{focs85v = {26}} @string{focs86 = {27th Annual Symposium on Foundations of Computer Science}} @string{focs86a = {Toronto, Ontario}} @string{focs86v = {27}} @string{focs87 = {28th Annual Symposium on Foundations of Computer Science}} @string{focs87a = {Los Angeles, California}} @string{focs87v = {28}} @string{focs88 = {29th Annual Symposium on Foundations of Computer Science}} @string{focs88a = {White Plains, New York}} @string{focs88v = {21}} @string{focs89 = {30th Annual Symposium on Foundations of Computer Science}} @string{focs89a = {Los Alamitos, Calif.}} @string{focs90 = {31st Annual Symposium on Foundations of Computer Science}} @string{focs91 = {32nd Annual Symposium on Foundations of Computer Science}} @string{focs92 = {33rd Annual Symposium on Foundations of Computer Science}} @string{focs92a = {Los Angeles, Calif.}} @string{fundi = {Fundamenta Informaticae}} @string{fundm = {Fundamenta Mathematicae}} @string{geom = {Proceedings of the Annual Symposium on Computational Geometry}} @string{geom85 = {Proceedings of the First Annual Symposium on Computational Geometry}} @string{geom85a = {Baltimore, Maryland}} @string{geom85v = {1}} @string{geom86 = {Proceedings of the Second Annual Symposium on Computational Geometry}} @string{geom86a = {Yorktown Heights, New York}} @string{geom86v = {2}} @string{geom87 = {Proceedings of the Third Annual Symposium on Computational Geometry}} @string{geom87a = {Waterloo, Ontario}} @string{geom87v = {3}} @string{geom88 = {Proceedings of the Fourth Annual Symposium on Computational Geometry}} @string{geom88a = {Urbana-Champaign, Illinois}} @string{geom88v = {4}} @string{hd = {Holden-Day, Inc.}} @string{hda = {San Francisco, California}} @string{iac = {Information and Computation}} @string{ic = {Information and Control}} @string{icalp = {International Colloquium on Automata, Languages, and Programming}} @string{icalp72 = {1st International Colloquium on Automata, Languages, and Programming}} @string{icalp72a = {Paris, France}} @string{icalp72v = {1}} @string{icalp74 = {2nd International Colloquium on Automata, Languages, and Programming}} @string{icalp74a = {Saarbr\"ucken, Germany}} @string{icalp74v = {2}} @string{icalp76 = {3rd International Colloquium on Automata, Languages, and Programming}} @string{icalp76a = {Edinburgh, Great Britain}} @string{icalp76v = {3}} @string{icalp77 = {4th International Colloquium on Automata, Languages, and Programming}} @string{icalp77a = {Turku, Finland}} @string{icalp77v = {4}} @string{icalp78 = {5th International Colloquium on Automata, Languages, and Programming}} @string{icalp78a = {Udine, Italy}} @string{icalp78v = {5}} @string{icalp79 = {6th International Colloquium on Automata, Languages, and Programming}} @string{icalp79a = {Gras, Austria}} @string{icalp79v = {6}} @string{icalp80 = {7th International Colloquium on Automata, Languages, and Programming}} @string{icalp80a = {Noordwijkerhout, The Netherlands}} @string{icalp80v = {7}} @string{icalp81 = {8th International Colloquium on Automata, Languages, and Programming}} @string{icalp81a = {Haifa, Israel}} @string{icalp81v = {8}} @string{icalp82 = {9th International Colloquium on Automata, Languages, and Programming}} @string{icalp82a = {Aarhus, Denmark}} @string{icalp82v = {9}} @string{icalp83 = {10th International Colloquium on Automata, Languages, and Programming}} @string{icalp83a = {Barcelona, Spain}} @string{icalp83v = {10}} @string{icalp84 = {11th International Colloquium on Automata, Languages, and Programming}} @string{icalp84a = {Antwerp, Belgium}} @string{icalp84v = {11}} @string{icalp85 = {12th International Colloquium on Automata, Languages, and Programming}} @string{icalp85a = {Nafplion, Greece}} @string{icalp85v = {12}} @string{icalp86 = {13th International Colloquium on Automata, Languages, and Programming}} @string{icalp86a = {Rennes, France}} @string{icalp86v = {13}} @string{icalp87 = {14th International Colloquium on Automata, Languages, and Programming}} @string{icalp87a = {Karlsruhe, Germany}} @string{icalp87v = {14}} @string{icalp88 = {15th International Colloquium on Automata, Languages, and Programming}} @string{icalp88a = {?}} @string{icalp88v = {15}} @string{icr = {Institute for Computer Research}} @string{icss = {International Computer Science Series}} @string{ieeetec = {IEEE Transactions on Electronic Computers}} @string{ieeetit = {IEEE Transactions on Information Theory}} @string{ifip71 = {Proceedings of IFIP Congress 71, Foundations of Information Processing}} @string{ijcis = {International Journal of Computer and Information Sciences}} @string{ijcm = {International Journal of Computer Mathematics}} @string{ije = {International Journal of Electronics}} @string{ijm = {Illinois Journal of Mathematics}} @string{ijtp = {International Journal of Theoretical Physics}} @string{inprep = {in preparation}} @string{inpress = {in press}} @string{ists59 = {Proceedings of the International Symposium on the Theory of Switching, Part II}} @string{ists59a = {Cambridge, Massachusetts}} @string{jams = {Journal of Australian Mathematics Society}} @string{jct = {Journal of Combinatorial Theory}} @string{jctsa = {Journal of Combinatorial Theory Series A}} @string{jctsb = {Journal of Combinatorial Theory Series B}} @string{jgt = {Journal of Graph Theory}} @string{jnt = {Journal of Number Theory}} @string{joa = {Journal of Algorithms}} @string{joc = {Journal of Complexity}} @string{jsl = {The Journal of Symbolic Logic}} @string{linalg = {Linear Algebra and its Applications}} @string{lmps64 = {Proceedings of the 1964 International Congress on Logic, Methodology, and Philosophy of Science}} @string{lncs = {Lecture Notes in Computer Science}} @string{lnems = {Lecture Notes in Economics and Mathematical Systems}} @string{lnm = {Lecture Notes in Mathematics}} @string{manual = {Manual}} @string{manuscr = {unpublished manuscript}} @string{mapol = {Mathesis Polska}} @string{matcomp = {Mathematics of Computation}} @string{mathann = {Mathematische Annalen}} @string{mathmag = {Mathematics Magazine}} @string{matpgm = {Mathematical Programming}} @string{mpcps = {Mathematical Proceedings of the Cambridge Philosophical Society}} @string{nacs2 = {NATO Conference Series II: Systems Science}} @string{nams = {Notices of the American Mathematical Society}} @string{nascib = {NATO Advanced Science Institute Series B: Physics}} @string{nascic = {NATO Advanced Science Institute Series C: Mathematical and Physical Sciences}} @string{nascie = {NATO Advanced Science Institute Series E: Applied Sciences}} @string{nascif = {NATO Advanced Science Institute Series F: Computer and System Sciences}} @string{nastic = {NATO Advanced Study Institute Series C: Mathematical and Physical Sciences}} @string{nastid = {NATO Advanced Study Institute Series D: Behavioural and Social Sciences}} @string{nh = {North-Holland Publishing Co.}} @string{nha = {Amsterdam}} @string{nmor = {National Meeting of the Operations Research Society of America}} @string{nmor59 = {16th National Meeting of the Operations Research Society of America}} @string{nmor59a = {Pasadena, California}} @string{nmor59v = {16}} @string{nrlq = {Naval Research Logistics Quarterly}} @string{nyas = {Annals of the New York Academy of Sciences}} @string{order = {Order}} @string{pams = {Proceedings of the American Mathematical Society}} @string{parcmp = {Parallel Computing}} @string{perscom = {personal communication}} @string{ph = {Prentice-Hall, Inc.}} @string{pha = {Englewood Cliffs, New Jersey}} @string{pjm = {Pacific Journal of Mathematics}} @string{qam = {Quarterly of Applied Mathematics}} @string{resrep = {Research Report}} @string{reston = {Reston Publishing Co.}} @string{restona = {Reston, Virginia}} @string{sciamer = {Scientific American}} @string{siam = {Society for Industrial and Applied Mathematics}} @string{siamdm = {SIAM Journal on Discrete Mathematics}} @string{siamsp = {SIAM-AMS Proceedings}} @string{sigact = {ACM Special Interest Group on Automata and Computability Theory}} @string{sigactn = {ACM SIGACT News}} @string{sija = {SIAM Journal of Algorithms}} @string{sijadm = {SIAM Journal on Algebraic and Discrete Methods}} @string{sijam = {SIAM Journal on Applied Mathematics}} @string{sijco = {SIAM Journal on Control and Optimization}} @string{sijma = {SIAM Journal on Mathematical Analysis}} @string{sijna = {SIAM Journal on Numerical Analysis}} @string{sijssc = {SIAM Journal on Scientific and Statistical Computing}} @string{sirev = {SIAM Review}} @string{sisam = {SIAM Studies in Applied Mathematics}} @string{smp78 = {Sparse Matrix Proceedings 1978}} @string{smz = {Sibirski\u{\i} Matematicheski\u{\i} Zhurnal}} @string{spring = {Spring}} @string{stoc = {Proceedings of the Annual ACM Symposium on Theory of Computing}} @string{stoc69 = {Proceedings of the First Annual ACM Symposium on Theory of Computing}} @string{stoc69a = {Marina del Rey, California}} @string{stoc69v = {1}} @string{stoc70 = {Proceedings of the Second Annual ACM Symposium on Theory of Computing}} @string{stoc70a = {Northampton, Massachusetts}} @string{stoc70v = {2}} @string{stoc71 = {Proceedings of the Third Annual ACM Symposium on Theory of Computing}} @string{stoc71a = {Shaker Heights, Ohio}} @string{stoc71v = {3}} @string{stoc72 = {Proceedings of the Fourth Annual ACM Symposium on Theory of Computing}} @string{stoc72a = {Denver, Colorado}} @string{stoc72v = {4}} @string{stoc73 = {Proceedings of the Fifth Annual ACM Symposium on Theory of Computing}} @string{stoc73a = {Austin, Texas}} @string{stoc73v = {5}} @string{stoc74 = {Proceedings of the Sixth Annual ACM Symposium on Theory of Computing}} @string{stoc74a = {Seattle, Washington}} @string{stoc74v = {6}} @string{stoc75 = {Proceedings of the Seventh Annual ACM Symposium on Theory of Computing}} @string{stoc75a = {Albuquerque, New Mexico}} @string{stoc75v = {7}} @string{stoc76 = {Proceedings of the Eighth Annual ACM Symposium on Theory of Computing}} @string{stoc76a = {Hershey, Pennsylvania}} @string{stoc76v = {8}} @string{stoc77 = {Proceedings of the Ninth Annual ACM Symposium on Theory of Computing}} @string{stoc77a = {Boulder, Colorado}} @string{stoc77v = {9}} @string{stoc78 = {Proceedings of the Tenth Annual ACM Symposium on Theory of Computing}} @string{stoc78a = {San Diego, California}} @string{stoc78v = {10}} @string{stoc79 = {Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing}} @string{stoc79a = {Atlanta, Georgia}} @string{stoc79v = {11}} @string{stoc80 = {Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing}} @string{stoc80a = {Los Angeles, California}} @string{stoc80v = {12}} @string{stoc81 = {Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing}} @string{stoc81a = {Milwaukee, Wisconsin}} @string{stoc81v = {13}} @string{stoc82 = {Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing}} @string{stoc82a = {San Francisco, California}} @string{stoc82v = {14}} @string{stoc83 = {Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing}} @string{stoc83a = {Boston, Massachusetts}} @string{stoc83v = {15}} @string{stoc84 = {Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing}} @string{stoc84a = {Washington, D. C.}} @string{stoc84v = {16}} @string{stoc85 = {Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing}} @string{stoc85a = {Providence, Rhode Island}} @string{stoc85v = {17}} @string{stoc86 = {Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing}} @string{stoc86a = {Berkeley, California}} @string{stoc86v = {18}} @string{stoc87 = {Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing}} @string{stoc87a = {New York, New York}} @string{stoc87v = {19}} @string{stoc88 = {Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing}} @string{stoc88a = {Chicago, Illinois}} @string{stoc88v = {20}} @string{stoc91 = {Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing}} @string{stoc91a = {New Orleans, Louisiana}} @string{stoc93 = {Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing}} @string{stoc93a = {New York, NY}} @string{struc86 = {Structure in Complexity Theory, Proceedings of the Conference}} @string{struc86a = {Berkeley, California}} @string{struc86e = {Alan L. Selman}} @string{struc86n = {Lecture Notes in Computer Science, Vol. 223}} @string{struc86v = {223}} @string{struc87 = {Proceedings, Structure in Complexity Theory, Second Annual Conference}} @string{struc87a = {Ithaca, New York}} @string{struc87v = {2}} @string{struc88 = {Proceedings, Structure in Complexity Theory, Third Annual Conference}} @string{struc88a = {Washington, D. C.}} @string{struc88v = {3}} @string{submit = {submitted for publication}} @string{summer = {Summer}} @string{sv = {Springer-Verlag}} @string{sva = {Berlin}} @string{swat88 = {SWAT 88 1st Scandinavian Workshop on Algorithm Theory}} @string{swat90 = {SWAT 90 2nd Scandinavian Workshop on Algorithm Theory}} @string{swat90a = {Bergen, Sweden}} @string{tams = {Transactions of the American Mathematical Society}} @string{tcj = {The Computer Journal}} @string{tcser = {Theory of Computation Series}} @string{techrep = {Technical Report}} @string{tgjie = {Th\'eorie des Graphes --- Journ\'ees Internationales d'\'Etude}} @string{tgjiea = {Rome, Italy}} @string{thinf = {Theoretical Informatics}} @string{tipsj = {Transactions of the Information Processing Society of Japan}} @string{tmt = {The Mathematics Teacher}} @string{toapp = {to appear}} @string{ualtacs = {University of Alberta Department of Computing Science}} @string{ubert = {Technische Universit\"at Berlin}} @string{uberta = {Technical University of Berlin, Department of Mathematics, StraBe des 17. Juni 135, 1000 Berlin 12}} @string{ucalst = {California State University}} @string{ucalsta = {San Jose, California}} @string{uchile = {Universidad de Chile}} @string{uchilea = {Santiago, Chile}} @string{ucm = {Carnegie-Mellon University}} @string{ucmcs = {Carnegie-Mellon University Department of Computer Science}} @string{uhp = {Harvard University Press}} @string{uhpa = {Cambridge, Massachusetts}} @string{uill = {University of Illinois}} @string{uilla = {Urbana, Illinois}} @string{uillp = {University of Illinois Press}} @string{ujh = {The Johns Hopkins University}} @string{ulund = {Lund University}} @string{ulunda = {Sweden}} @string{umin = {University of Minnesota}} @string{uminst = {University of Minnesota Department of Statistics}} @string{uoxp = {Oxford University Press, Inc.}} @string{ustan = {Stanford University}} @string{utor = {University of Toronto}} @string{utorcs = {University of Toronto Department of Computer Science}} @string{uwat = {University of Waterloo}} @string{uwatcs = {University of Waterloo Department of Computer Science}} @string{wb = {Wadsworth \& Brooks}} @string{wba = {Monterey, California}} @string{whf = {W. H. Freeman and Company}} @string{whfa = {San Francisco, California}} @string{wiley = {John Wiley \& Sons, Inc.}} @string{wileya = {New York, New York}} @string{winter = {Winter}} @article( abn61 ,author= {J. S. Appleby and D. V. Blake and E. A. Newman} ,title= {Techniques for Producing School Timetables on a Computer and their Application to Other Scheduling Problems} ,journal= tcj ,year= 1961 ,volume= 3 ,pages= {237--245} ,keywords= {graph coloring related} ,classif= {Coloring Applications--Timetable} ) @article( adp80 ,author= {G. Ausiello and A. D'Atri and M. Protasi} ,title= {Structure Preserving Reductions Among Convex Optimization Problems} ,journal= jcss ,year= 1980 ,volume= 21 ,pages= {136--153} ,keywords= {graph coloring related topics clique approximation complexity} ) @article( ahk77 ,author= {K. Appel and W. Haken and J. Koch} ,title= {Every Planar Map is Four Colorable Part {II}: Reducibility} ,journal= ijm ,year= 1977 ,volume= 21 ,pages= {491--567} ,keywords= {graph color} ,annote= {This is the second part of the proof of the four color problem.} ) @article( ake74 ,author= {Akers, Jr., Sheldon B.} ,title= {Fault Diagnosis as a Graph Coloring Problem} ,journal= ieeetc ,year= 1974 ,volume= {c-23} ,number= 7 ,pages= {706--712} ,month= jul ,keywords= {graph coloring} ) @article( akk73 ,author= {E. A. Akkoyunlu} ,title= {The Enumeration of Maximal Cliques of Large Graphs} ,journal= sicomp ,year= 1973 ,volume= 2 ,number= 1 ,pages= {1--6} ,month= mar ,keywords= {maximum clique algorithm} ) @incollection( almss92 ,author= {Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu Sudan and Mario Szegedy} ,title= {Proof Verification and Hardness of Approximation Problems} ,booktitle= focs92 ,year= 1992 ,pages= {14--23} ,publisher= {IEEE Computer Society Press} ,address= {Los Alamitos, CA} ,keywords= {NP} ) @article( ani86 ,author= {Anisimov, A. V.} ,title= { Local Optimization of Colorings of Graphs} ,journal= { Cybernetics} ,year= 1986 ,volume= 22 ,number= 6 ,pages= {683--692} ,note= {Translated from Kibernetika, No. 6, pp. 1---8, Nov-Dec, 1986} ,keywords= {graph color} ,mrnumbers= {88k#05077} ) @article( apha76 ,author= {K. Appel and W. Haken} ,title= {Every Planar Map is Four Colorable} ,journal= {American Mathematical Society Bulletin} ,year= 1976 ,volume= 82 ,number= 5 ,pages= {711--712} ,keywords= {graph coloring four color theorem} ) @article( apha77 ,author= {K. Appel and W. Haken} ,title= {Every Planar Map is Four Colorable Part {I}: Discharging} ,journal= ijm ,year= 1977 ,volume= 21 ,pages= {429--490} ,keywords= {graph color} ,annote= {This is the first part of the proof of the four color problem.} ) @article( apha86 ,author= {K. Appel and W. Haken} ,title= {The Four Color Proof Suffices} ,journal= {The Mathematical Intellegencer} ,year= 1986 ,volume= 8 ,number= 1 ,pages= {10--20 \& 58} ,keywords= {graph coloring four color theorem} ,annote= {This is a discussion of the proof of the Four Color Theorem.} ) @book( apha89 ,author= {Kenneth Appel and Wolfgang Haken} ,title= {Every Planar Map is Four Colorable} ,publisher= {American Mathematical Society} ,year= 1989 ,volume= 98 ,series= {Contemporary Mathematics} ,address= {Providence, RI} ,keywords= {four color problem proof} ,annote= {This book presents the background and proof of the four color problem.} ,classif= {MATH LIB QA612.18 A646 1989} ) @techreport( arj80 ,author= {E. Arjomandi} ,title= { An Efficient Algorithm for Colouring the Edges of a Graph with Delta + 1 Colours} ,institution= {York University, Department of Computer Science} ,year= 1980 ,type= techrep ,number= {1} ,note= {Subfile: STR (Stanford Technical Reports)} ,keywords= {graph color} ) @incollection( arsa92 ,author= {Sanjeev Arora and Shmuel Safra} ,title= {Probabilistic Checking or Proofs; A New Characterization of {NP}} ,booktitle= focs92 ,year= 1992 ,pages= {2--13} ,publisher= {IEEE Computer Society Press} ,address= {Los Alamitos, CA} ,keywords= {clique NP} ) @article( asgi84 ,author= {Bengt Aspvall and John R. Gilbert} ,title= { Graph Coloring Using Eigenvalue Decomposition} ,journal= sijadm ,year= 1984 ,volume= 5 ,number= 4 ,month= dec ,pages= {526--538} ,mrnumbers= { 86a#05044} ) @article( aumi70 ,author= {J. Gary Augustson and Jack Minker} ,title= {An Analysis of Some Graph Theoretical Cluster Techniques} ,journal= jacm ,year= 1970 ,volume= 17 ,number= 4 ,pages= {571--588} ,month= oct ,keywords= {clique} ,note= {See also [muco72].} ) @article( bab91 ,author= {L. Babel} ,title= {Finding Maximum Cliques in Arbitrary and in Special Graphs} ,journal= comp ,year= 1991 ,volume= 46 ,pages= {321--341} ,keywords= {maximum clique algorithm} ) @techreport( baev83 ,author= {R. Bar-Yehuda and S. Even} ,title= {A $2-{{\log\log n} \over {2 \log n}}$ Performance Ratio for the Weighted Vertex Cover Problem} ,institution= {Technion Haifa} ,year= 1983 ,type= techrep ,number= {\#260} ,month= jan ,note= {NCPY} ,keywords= {graph coloring} ) @incollection( baju85 ,author= {F. Bauern\"{o}ppel and H. Jung} ,title= {Fast Parallel Vertex Colouring} ,booktitle= {Fundamentals of Computation Theory, FCT '85, Cottbus, GDR, Sept, 1985} ,year= 1985 ,editor= {Lothar Budach} ,pages= {28--35} ,publisher= sv ,address= sva ,series= lncs ,volume= 199 ,keywords= {graph coloring parallel algorithm} ) @article( bal90 ,author= {Pierre Baldi} ,title= {On a Generalized Family of Colorings} ,journal= {Graphs and Combinatorics} ,year= 1990 ,volume= 6 ,pages= {95--110} ,keywords= {graph coloring} ) @article( bapo90 ,author= {Pierre Baldi and Edward C. Posner} ,title= { Graph Coloring Bounds for Cellular Radio} ,journal= cmpmth ,year= 1990 ,volume= 19 ,number= 10 ,pages= {91--97} ,classif= {Coloring Applications--Timetable} ) @article( baxu91 ,author= {Egon Balas and Jue Xue} ,title= {Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs} ,journal= sicomp ,year= 1991 ,volume= 20 ,number= 2 ,pages= {209--221} ,month= apr ,keywords= {graph coloring maximum clique algorithm} ) @article( bayu86 ,author= {Egon Balas and Chang Sung Yu} ,title= {Finding a Maximum Clique in an Arbitrary Graph} ,journal= sicomp ,year= 1986 ,volume= 15 ,number= 4 ,month= nov ,pages= {1054--1068} ,keywords= {algorithm based on triangulated graph properties} ,classif= {Cliques and Independent Sets} ) @incollection( bckt89 ,author= {P. Briggs and K. Cooper and K. Kennedy and L. Torczon} ,title= {Coloring Heuristics for Register Allocation} ,booktitle= {ASCM Conference on Program Language Design and Implementation} ,publisher= acm ,year= 1989 ,editor= {} ,pages= {275--284} ,address= {} ,keywords= {graph coloring heuristic algorithms} ,series= {} ,volume= {} ,classif= {Referenced in DIMACS Cliques and Colorings Bibliography.} ) @article( bcn87 ,author= {Egon Balas and Va\v{s}ek Chv\'{a}tal and Jaroslav Ne\v{s}et\v{r}il} ,title= {On the Maximum Weight Clique Problem} ,journal= {Mathematics of Operations Research} ,year= 1987 ,volume= 12 ,number= 3 ,month= aug ,pages= {522--535} ,keywords= {clique} ) @article( bea76 ,author= {D. Bean} ,title= {Effective Coloration} ,journal= jsl ,volume= 41 ,number= 2 ,year= 1976 ,pages= {469--480} ,month= jun ,keywords= {graph coloring related theory} ) @incollection( bech78 ,author= {James M. Benedict and Phyllis Zweig Chinn} ,title= {On Graphs Having Prescribed Clique Number, Chromatic Number, and Maximum Degree} ,booktitle= {Theory and Applications of Graphs (Proceedings, Michigan, May, 1976)} ,publisher= sv ,year= 1978 ,editor= {Y. Alavi and D. R. Lick} ,pages= {132--140} ,address= sva ,keywords= {graph coloring chromatic number clique number degree} ,series= lnm ,volume= 642 ) @article( bedu84 ,author= {C. Berge and P. Duchet} ,title= {Strongly Perfect Graphs} ,journal= adm ,year= 1984 ,volume= 21 ,pages= {57--61} ,keywords= {graph coloring} ) @incollection( ber78 ,author= {Claude Berge} ,title= {Algorithms and Extremal Problems for Equipartite Colorings in Graphs and Hypergraphs (abstract)} ,booktitle= {Algorithmic Aspects of Combinatorics} ,editor= {B. Alspach and P. Hell and D. J. Miller} ,pages= {149--150} ,publisher= nh ,year= 1978 ,volume= 2 ,series= adm ,keywords= {graph color} ) @article( bero90 ,author= {Bonnie Berger and John Rompel} ,title= { A Better Performance Guarantee for Approximate Graph Coloring} ,journal= algo ,year= 1990 ,volume= 5 ,number= 4 ,pages= {459--466} ,classif= {Approximate Algorithms--Worst Case Guarantees} ) @article( bewi85 ,author= { Edward A. Bender and Herbert S. Wilf} ,title= { A Theoretical Analysis of Backtracking in the Graph Coloring Problem} ,journal= joa ,year= 1985 ,volume= 6 ,number= 2 ,pages= {275--282} ,mrnumbers= { 86j#05057} ) @article( bire75 ,author= {J. R. Bitner and E. Reingold} ,title= {Backtrack Programming Techniques} ,journal= cacm ,year= 1975 ,volume= 18 ,pages= {651--656} ,keywords= {graph coloring related algorithms} ) @article( bjkr90 ,author= {A. D. Barbour and Svante Janson and Michal Karo\'{n}ski and Andrzej Ruci\'{n}ski} ,title= {Small Cliques in Random Graphs} ,journal= {Random Structures and Algorithms} ,year= 1990 ,volume= 1 ,number= 4 ,pages= {403--434} ,keywords= {graph coloring related theory} ,classif= {Random Graphs and Chromatic Number} ) @article( bksw90 ,author= {Jason I. Brown and David Kelly and J. Sch\"{o}nheim and Robert E. Woodrow} ,title= { Graph Coloring Satisfying Restraints} ,journal= dm ,year= 1990 ,volume= 80 ,number= 2 ,pages= {123--143} ,mrnumbers= {91c#05075} ) @inproceedings( blu89 ,author= {Avrim Blum} ,title= {An $\tilde{O}(n^{0.4})$-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithms for $k$-Coloring)} ,booktitle= {Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing} ,year= 1989 ,pages= {535--542} ,keywords= {graph coloring } ,classif= {Approximate Algorithms--Worst Case Guarantees} ) @incollection( blu90 ,author= {Avrim Blum} ,title= {Some Tools for Approximate 3-Coloring} ,booktitle= focs90 ,year= 1990 ,pages= {554--562} ,publisher= {IEEE Computer Society Press} ,address= {Los Alamitos, CA} ,keywords= {graph coloring approximation algorithm} ) @incollection( bms80 ,author= {E. Burattini and A. Massarotti and A. Santaniello} ,title= { A Graph Colouration Technique} ,booktitle= {Applications of Information and Control Systems (Volume III of a Selection of Papers from INFO II, the Second International Conference on Information Sciences and Systems, University of Patras, Greece, July 1979)} ,year= 1980 ,pages= {326--333} ,publisher= {Reidel Publishing Co.} ,keywords= {graph color} ,mrnumbers= { 82g#05045} ) @incollection( bod91 ,author= {Hans L. Bodlaender} ,title= {On the Complexity of Some Coloring Games} ,booktitle= {Graph-Theoretic Concepts in Computer Science (Proceedings of the 16th International Workshop WG '90, Berlin, Germany, June, 1990)} ,year= 1991 ,editor= {R. H. M\"{o}hring} ,pages= {30--40} ,publisher= sv ,address= sva ,series= lncs ,volume= 484 ,keywords= {graph coloring} ) @article( boer76 ,author= {B. Bollob\'{a}s and P. Erd\"{o}s} ,title= {Cliques in Random Graphs} ,journal= mpcps ,year= 1976 ,volume= 80 ,number= 41 ,pages= {419--427} ,keywords= {graph coloring related clique theory} ,classif= {Cliques and Independent Sets} ) @article( boha85 ,author= {B\'{e}la Bollob\'{a}s and A. J. Harris} ,title= {List-Colourings of Graphs} ,journal= {Graphs and Combinatorics} ,year= 1985 ,volume= 1 ,number= 2 ,pages= {115--127} ,keywords= {graph coloring} ) @inproceedings( boha90 ,author= {Ravi Boppana and Magn\'{u}s M. Halld\'{o}rsson} ,title= {Approximating Maximum Independent Sets by Excluding Subgraphs} ,booktitle= swat90 ,editor= {J. R. Gilbert and R. Karlsson} ,year= 1990 ,pages= {13--25} ,series= lncs ,volume= 447 ,keywords= {graph coloring related clique approximation complexity} ,annote= {Guarantees $O(n/(\log n)^2)$ approximation)} ) @article( boka87 ,author= {Joan F. Boyar and Howard J. Karloff} ,title= {Coloring Planar Graphs in Parallel} ,journal= joa ,year= 1987 ,volume= 8 ,pages= {470--479} ,keywords= {graph color} ,classif= {Planar/Parallel Coloring} ) @article( bol78 ,author= {B\'{e}la Bollob\'{a}s} ,title= {Chromatic Number, Girth and Maximal Degree} ,journal= dm ,year= 1978 ,volume= 24 ,pages= {311--314} ,keywords= {graph coloring theory probabilistic method} ,classif= {Theoretical} ) @article( bol88 ,author= {B\'{e}la Bollob\'{a}s} ,title= {The Chromatic Number of Random Graphs} ,journal= comb ,year= 1988 ,volume= 8 ,number= 1 ,pages= {49--55} ,keywords= {graph color} ) @article( bon69 ,author= {J. A. Bondy} ,title= {Bounds for the chromatic number of a graph} ,journal= jct ,year= 1969 ,volume= 7 ,pages= {96--98} ,keywords= {graph color} ) @article( both79 ,author= {B\'{e}la Bollob\'{a}s and Andrew Thomason} ,title= {Set Colourings of Graphs} ,journal= dm ,year= 1979 ,volume= 25 ,pages= {21--26} ,keywords= {graph coloring sets} ) @incollection( both85 ,author= {B\'{e}la Bollob\'{a}s and Andrew Thomason} ,editor= {Micha{\l} Karo\'{n}ski and Andrzej Ruci\'{n}ski} ,title= {Random Graphs of Small Order} ,booktitle= {Random Graphs '83} ,publisher= nh ,address= {Amsterdam} ,year= 1985 ,pages= {47--97} ,keywords= {graph color} ,series= adm ,volume= 28 ,classif= {Heuristic Coloring} ) @article( bre79 ,author= {Daniel Br\'{e}laz} ,title= {New Methods to Color the Vertices of a Graph} ,journal= cacm ,year= 1979 ,volume= 22 ,number= 4 ,pages= {251--256} ,month= apr ,keywords= {graph color dsatur} ) @article( brke73 ,author= {Coen Bron and Joep Kerbosch} ,title= {Algorithm 457: Finding all Cliques of an Undirected Graph {[H]}} ,journal= cacm ,year= 1973 ,volume= 16 ,number= 9 ,month= sep ,pages= {575-577} ,keywords= {graph coloring related clique backtracking branch and bound} ,classif= {Cliques and Independent Sets} ) @article( bro41 ,author= {R. L. Brooks} ,title= {On Colouring the Nodes of a Network} ,journal= mpcps ,year= 1941 ,volume= 37 ,month= apr ,pages= {194--197} ,keywords= {graph color} ) @article( bro64 ,author= {Sol Broder} ,title= {Final Examination Scheduling} ,journal= cacm ,year= 1964 ,volume= 7 ,number= 8 ,pages= {494--498} ,month= aug ,keywords= {graph coloring related} ,classif= {Coloring Applications--Timetable} ) @article( bro72 ,author= {J. Randall Brown} ,title= {Chromatic Scheduling and the Chromatic Number Problem} ,journal= {Management Science} ,year= 1972 ,volume= 19 ,number= 4 ,pages= {456--463} ,month= {December, Part I} ,keywords= {graph color} ,classif= {Coloring Algorithms--Exact} ) @incollection( buma82 ,author= {C. Butler and L. R. Matthews} ,title= {An Application of Graph Colouring on the Railways} ,booktitle= {Applications of Combinatorics} ,publisher= {Shiva Publishing Ltd.} ,year= 1982 ,editor= {R. J. Wilson} ,chapter= 2 ,pages= {19--28} ,address= {Cheshire, England} ,keywords= {graph coloring application} ) @article( cacchm81 ,author= {Gregory J. Chaitin and Marc A. Auslander and Ashok K. Chandra and John Cocke and Martin E. Hopkins and Peter W. Markstein} ,title= {Register Allocation via Coloring} ,journal= {Computer Languages} ,year= 1981 ,volume= 6 ,pages= {47--57} ,keywords= {graph coloring} ) @article( capa90 ,author= {Randy Carraghan and Panos M. Pardalos} ,title= {An Exact Algorithm for the Maximum Clique Problem} ,journal= {Operations Research Letters} ,year= 1990 ,volume= 9 ,pages= {375--382} ,keywords= {graph coloring related algorithms clique} ,classif= {Cliques and Independent Sets} ) @incollection( car74 ,author= {Raul Carvajal} ,title= {Modulus {K} Check Digits and the Chromatic Number Problem} ,booktitle= {Information Processing 74 (Proceedings of IFIP Congress, Stockholm, Sweden, August, 1974)} ,year= 1974 ,editor= {J. L. Rosenfeld} ,pages= {521--523} ,publisher= nh ,keywords= {graph coloring} ) @article( cat85 ,author= {Paul A. Catlin} ,title= {Homomorphisms as a Generalization of Graph Coloring} ,journal= connum ,year= 1985 ,volume= 50 ,pages= {179--186} ,mrnumbers= {87f#05066} ) @article( cath85 ,author= { Cameron, Jane and Thomas, Gomer} ,title= {An Approximate Graph Partitioning Algorithm and Its Computational Complexity} ,journal= connum ,year= 1985 ,volume= 49 ,pages= {287--293} ,keywords= {graph color} ,mrnumbers= { 87m#05106} ,classif= {Heuristic Coloring} ) @article (ceg88 ,author = {N.E. Collins and R.W. Eglese and B.L. Golden} ,journal= {American Journal of Mathematical and Management Sciences} ,pages= {205--307} ,title= {Simulated Annealing: An Annotated Bibliography} ,volume= 8 ,year= {1988} ,ccreview= {Very large and complete (circa 1988) bibliography of the state of simulated annealing.} ) @incollection( cgj78 ,author= {V. Chv\'{a}tal and M. R. Garey and D. S. Johnson} ,title= {Two Results Concerning Multicoloring} ,booktitle= {Algorithmic Aspects of Combinatorics} ,editor= {B. Alspach and P. Hell and D. J. Miller} ,publisher= nh ,year= 1978 ,pages= {151--154} ,keywords= {graph color} ,series= adm ,volume= 2 ) @article( cha82 ,author= {Gregory J. Chaitin } ,title= {Register Allocation and Spilling via Graph Coloring} ,journal= {SIGPLAN Notices (Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass.)} ,year= 1982 ,volume= 17 ,number= 6 ,month= jun ,pages= {98--105} ,keywords= {graph coloring application} ) @inproceedings( che86 ,author= {Cheban, Ya. I.} ,title= {Investigation of a Generalized Graph Coloring Problem} ,booktitle= {Investigation of Methods for Solving Extremal Problems (Russian)} ,year= 1986 ,pages= {77--81} ,organization= { Akad. Nauk Ukrain. SSR, Inst. Kibernet., Kiev} ,series= {vii} ,mrnumbers= { 88d#05057} ) @article( chhe90 ,author= {Fred C. Chow and John L. Hennessy} ,title= {The Priority--Based Coloring Approach to Register Allocation} ,journal= toplas ,year= 1990 ,volume= 12 ,number= 4 ,pages= {501--536} ,month= oct ,keywords= {graph coloring algorithm chromatic number} ) @article( chl87 ,author= { Campers, G. and Henkes, O. and Leclercq, J. P.} ,title= { Sur les methodes exactes de coloration de graphes. {O}n exact methods of graph coloring} ,journal= ccero ,year= 1987 ,volume= 29 ,number= {1--2} ,pages= {19--30} ,keywords= {graph color} ,mrnumbers= {88k#05078} ) @incollection( chl88 ,author= {G. Campers and O. Henkes and J. P. Leclerq} ,editor= {G. K. Rand} ,title= {Graph Coloring Heuristics: A Survey, Some New Propositions and Computational Experiences on Random and ``{L}eighton's'' Graphs} ,booktitle= { Operational research '87 (Buenos Aires, 1987) } ,publisher= nh ,year= 1988 ,pages= {917--932} ,mrnumbers= { 90d#05095} ) @article( chmw87 ,author= {V. Chv\'{a}tal and C. T. Ho\`{a}ng and N. V. R. Mahadev and D. de Werra} ,title= {Four Classes of Perfectly Orderable Graphs} ,journal= jgt ,year= 1987 ,volume= 11 ,number= 4 ,pages= {481--495} ,keywords= {graph coloring related theory} ) @article( chr71 ,author= {N. Christofides} ,title= {An Algorithm for the Chromatic Number of a Graph} ,journal= tcj ,year= 1971 ,volume= 14 ,number= 1 ,pages= {38--39} ,keywords= {graph color} ,classif= {Coloring Algorithms--Exact} ) @article( chsl84 ,author= {M. Chrobak and M. \'{S}lusarek} ,title= {Problem 84-23} ,journal= joa ,year= 1984 ,volume= 5 ,pages= {588} ,keywords= {related to graph coloring} ,annote= {This is a problem concerning a wall which is defined as a finite set of triples called bricks.} ) @incollection( chv84 ,author= {V. Chv\'{a}tal} ,title= {Perfectly Ordered Graphs} ,booktitle= {Topics on Perfect Graphs} ,pages= {63--65} ,publisher= nh ,year= 1984 ,editor= {C. Berge and V. Chv\'{a}tal} ,series= adm ,keywords= {graph coloring related theory} ,volume= 21 ) @article( chw87 ,author= {M. Chams and A. Hertz and D. de Werra} ,title= {Some experiments with simulated annealing for coloring graphs} ,journal= ejor ,year= 1987 ,volume= 32 ,number= 2 ,pages= {260--266} ,keywords= {graph color} ,mrnumbers= {88i#90079} ,classif= {Coloring--Annealing/Tabu} ) @inproceedings( ckt91 ,author= {Peter Cheeseman and Bob Kanefsky and William M. Taylor} ,title= {Where the {\em Really} Hard Problems Are} ,booktitle= {International Joint Conference on Artificial Intelligence} ,year= 1991 ,pages= {331--337} ,classif= {Hard and Easy Coloring} ) @article( clel83 ,author= {A. T. Clementson and C. H. Elphick} ,title= {Approximate Colouring Algorithms for Composite Graphs} ,journal= {Journal of the Operational Research Society} ,year= 1983 ,volume= 34 ,number= 6 ,pages= {503--509} ,keywords= {graph coloring school timetable approximate algorithm} ) @article( cns81 ,author= {Norishige Chiba and Takao Nishizeki and Nobuji Saito} ,title= {A Linear $5$-Coloring Algorithm of Planar Graphs} ,journal= joa ,year= 1981 ,volume= 2 ,number= 4 ,pages= {317--327} ,keywords= {linear algorithm graph coloring} ) @article( cogr73 ,author= {D. G. Corneil and B. Graham} ,title= {An Algorithm for Determining the Chromatic Number of a Graph} ,journal= sicomp ,year= 1973 ,volume= 2 ,number= 4 ,pages= {311--318} ,month= dec ,keywords= {graph color} ,classif= {Coloring Algorithms--Heuristic} ) @article( coho82 ,author= {Richard Cole and John Hopcroft} ,title= {On Edge Coloring Bipartite Graphs} ,journal= sicomp ,year= 1982 ,volume= 11 ,number= 3 ,pages= {540--546} ,month= aug ,keywords= {edge coloring} ) @article( col64 ,author= {A. J. Cole} ,title= {The Preparation of Examination Time-Tables Using a Small-Store Computer} ,journal= tcj ,year= 1964 ,volume= 7 ,pages= {117--121} ,keywords= {graph color} ,classif= {Coloring Applications--Timetable} ) @article( como83 ,author= {Thomas F. Coleman and Jorge J. More} ,title= {Estimation of Sparse {J}acobian Matrices and Graph Coloring Problems} ,journal= sijna ,year= 1983 ,volume= 20 ,number= 1 ,month= feb ,pages= {187--209} ) @article( como84 ,author= {Thomas F. Coleman and Jorge J. More} ,title= { Estimation of Sparse {H}essian Matrices and Graph Coloring Problems} ,journal= matpgm ,year= 1984 ,volume= 28 ,number= 3 ,pages= {243--270} ,mrnumbers= { 85d#65041} ) @article( coo75 ,author= {R. J. Cook} ,title= {Chromatic Number and Girth} ,journal= {Periodica Mathematica Hungarica} ,year= 1975 ,volume= 6 ,number= 1 ,pages= {103--107} ,keywords= {graph coloring theory} ,classif= {Theoretical} ) @techreport( cul92 ,author= {Joseph C. Culberson} ,title= {Iterated Greedy Graph Coloring and the Difficulty Landscape} ,institution= ualtacs ,year= 1992 ,type= techrep ,number= {TR 92-07} ,address= {Edmonton, Alberta, Canada T6G 2H1} ,note= {ftp ftp.cs.ualberta.ca pub/TechReports} ) @article( dai80 ,author= {D. P. Dailey} ,title= {Uniqueness of Colorability and Colorability of Planar 4-Regular Graphs are {NP}-Complete} ,journal= dm ,year= 1980 ,volume= 30 ,pages= {289--293} ,keywords= {graph color} ) @article( ddh84 ,author= {Peter Dencker and Karl D\"{u}rre and Johannes Heuft} ,title= { Optimization of Parser Tables for Portable Compilers} ,journal= toplas ,year= 1984 ,volume= 6 ,number= 4 ,pages= {546--572} ,keywords= {graph color} ) @incollection( dem71 ,author= {M. A. H. Dempster} ,title= {Two Algorithms for the Time-Table Problem} ,booktitle= {Combinatorial Mathematics and its Applications (Proceedings of a Conference held at the Mathematical Institute, Oxford, July, 1969)} ,year= 1971 ,editor= {D. J. A. Welsh} ,pages= {63--85} ,publisher= ap ,address= {London} ,keywords= {graph coloring time-table} ) @article( des47 ,author= {Blanches Descartes} ,title= {A Three Colour problem} ,journal= {Eureka} ,year= 1947 ,month= apr ,note= {solution march 1948; pseudonym for Tutte} ,keywords= {graph coloring theory girth} ) @article( des54 ,author= {Blanches Descartes} ,title= {Solution to Advanced Problem 4526, proposed by {P}eter {U}ngar} ,journal= amm ,year= 1954 ,volume= 61 ,pages= {352--353} ,note= {psuedonym for Tutte} ,keywords= {graph coloring theory girth} ) @inproceedings( dhm82 ,author= {K. D\"{u}rre and J. Heuft and H. M\"{u}ller} ,title= { Worst and Best Case Behaviour of an Approximate Graph Coloring Algorithm} ,booktitle= { Proceedings of the 7th Conference on Graphtheoretic Concepts in Computer Science, Linz, Austria, June, 1981} ,year= 1982 ,editor= {J. R. Muhlbacher and Carl Hansen Verlag} ,pages= {339-348} ,keywords= {graph coloring algorithm chromatic number} ) @article( dhu89 ,author= {Medha Dhurandhar} ,title= {On the Chromatic Number of a Graph with Two Forbidden Subgraphs} ,journal= jctsb ,year= 1989 ,volume= 46 ,pages= {1--6} ,keywords= {chromatic number graph coloring} ) @incollection( dik86 ,author= {Krzysztof Diks} ,title= { A Fast Parallel Algorithm for Six-Colouring of Planar Graphs (Extended Abstract)} ,booktitle= { Mathematical Foundations of Computer Science 1986 (Proceedings of the Twelfth Symposium Held in Bratislava, Czechoslovakia)} ,year= 1986 ,editor= {J. Gruska and B. Rovan and J. Wiedermann} ,pages= {273--282} ,publisher= sv ,address= sva ,series= lncs ,volume= 233 ,keywords= {graph color} ,mrnumbers= { 87m#68008} ,classif= {Planar/Parallel Coloring} ) @article( dir53 ,author= {G. A. Dirac} ,title= {The Structure of k-Chromatic Graphs} ,journal= fundm ,year= 1953 ,volume= 40 ,pages= {42--55} ,note= {color} ) @article( dir57 ,author= {G. A. Dirac} ,title= {A Theorem of {R. L. Brooks} and a Conjecture of {H. Hadwiger}} ,journal= {Proceedings of the London Mathematical Society} ,year= 1957 ,volume= 3 ,number= 7 ,pages= {161--195} ,keywords= {graph coloring related theory} ) @incollection( dowe84 ,author= {Peter Donnelly and Dominic Welsh} ,editor= {B\'{e}la Bollob\'{a}s} ,booktitle= {Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference---A Volume in Honour of {P}aul {E}rd\"{o}s} ,title= {The Antivoter Problem: Random 2-Colourings of Graphs} ,pages= {133--144} ,publisher= ap ,year= 1984 ,keywords= {graph coloring related theory} ,classif= {Theoretical} ) @article( dubr81 ,author= {R. D. Dutton and R. C. Brigham} ,title= {A New Graph Colouring Algorithm} ,journal= tcj ,year= 1981 ,volume= 24 ,number= 1 ,pages= {85--86} ,classif= {Heuristic Coloring} ) @incollection( dun76 ,author= {F. D. J. Dunstan} ,title= {Sequential Colourings of Graphs} ,booktitle= {Proceedings of Fifth British Combinatorial Conference, University of Aberdeen, July, 1975} ,year= 1976 ,pages= {151--158} ,editor= {C. Nash-Williams and J. Sheehan} ,publisher= {Utilitas Mathematica} ,address= {Winnipeg} ,keywords= {graph color} ) @incollection( dur73 ,author= {K. D\"{u}rre} ,title= {An Algorithm for Coloring the Vertices of an Arbitrary Finite Graph} ,booktitle= {GI Gesellschaft f\"{u}r Informatik e.V. 2. Jahrestagung, Karlsruhe, Oktober, 1972} ,publisher= sv ,address= sva ,year= 1973 ,editor= {Peter Deussen} ,pages= {82--89} ,keywords= {graph color} ,series= lnems ,volume= 78 ) @incollection( dyfr86 ,author= {M. E. Dyer and A. M. Frieze} ,title= {Fast Solution of Some Random {NP}-Hard Problems (Extended Abstract)} ,booktitle= focs86 ,year= 1986 ,pages= {331--336} ,publisher= {IEEE Computer Society Press} ,address= {Los Alamitos, CA} ,keywords= {graph coloring related theory} ,classif= {Hard and Easy Coloring} ) @article( dyfr89 ,author= {M. E. Dyer and A. M. Frieze} ,title= {The Solution of Some Random {NP}-Hard problems in Polynomial Expected Time} ,journal= joa ,year= 1989 ,volume= 10 ,pages= {451--489} ,keywords= {graph coloring related topics} ,classif= {Hard and Easy Coloring} ) @phdthesis( ear68 ,author= {S. Early} ,title= {Evaluating a Timetabling Algorithm Based on Graph Recolouring} ,school= {University of Oxford} ,year= 1968 ,note= {B. Phil. Diss.} ) @article( eis76 ,author= {S. Even and A. Itai and A. Shamir} ,title= {On the Complexity of Timetable and Multicommodity Flow Problems} ,journal= sicomp ,year= 1976 ,volume= 5 ,number= 4 ,pages= {691--703} ,month= dec ,keywords= {timetable problem algorithm} ) @article( elle89 ,author= {J. A. Ellis and P. M. Lepolesa} ,title= {A {L}as {V}egas Graph Coloring Algorithm} ,journal= tcj ,year= 1989 ,volume= 32 ,number= 5 ,pages= {474--476} ,keywords= {graph color} ,classif= {Heuristic Coloring} ) @article( erd59 ,author= {P. Erd\"{o}s} ,title= {Graph Theory and Probability} ,journal= cjm ,year= 1959 ,volume= 11 ,pages= {34--38} ,keywords= {graph coloring related theory} ) @article( erd62 ,author= {P. Erd\"{o}s} ,title= {On Circuits and Subgraphs of Chromatic Graphs} ,journal= {Mathematika} ,year= 1962 ,volume= 9 ,pages= {170--175} ,keywords= {graph coloring related theory} ) @article( erer86 ,author= {Marcel Erne and Paul Erd\"{o}s} ,title= {Clique Numbers of Graphs} ,journal= dm ,year= 1986 ,volume= 59 ,number= 3 ,pages= {235--241} ,keywords= {graph coloring related clique theory} ) @article( erwi77 ,author= {P. Erd\"{o}s and R. J. Wilson} ,title= {On the Chromatic Index of Almost All Graphs} ,journal= jctsb ,year= 1977 ,volume= 23 ,pages= {255--257} ,keywords= {graph color} ) @inproceedings( femo91 ,author= {Tom\'{a}s Feder and Rajeev Motwani} ,title= {Clique Partitions, Graph Compression and Speeding-Up Algorithms} ,booktitle= {Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, New Orleans, Louisiana, May, 1991} ,year= 1991 ,pages= {123--133} ,keywords= {graph coloring related topics} ) @inproceedings( fglss91 ,author= {U. Feige and S. Goldwasser and L. Lov\'{a}sz and S. Safra and M. Szegedy} ,title= {Approximating Clique is Almost {NP}-Complete} ,booktitle= {Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, Oct, 1991} ,year= 1991 ,pages= {2--12} ,keywords= {graph coloring related theory clique approximation complexity} ) @article( fhhm86 ,author= {Martin Farber and Ge\v{n}a Hahn and Pavol Hell and Donald Miller} ,title= {Concerning the Achromatic Number of Graphs} ,journal= jctsb ,year= 1986 ,volume= 40 ,pages= {21--39} ,keywords= {graph coloring achromatic number} ) @article( fhw89 ,author= {C. Friden and A. Hertz and D. de Werra} ,title= {{STABULUS:} {A} Technique for Finding Stable Sets in Large Graphs with Tabu Search} ,journal= comp ,year= 1989 ,volume= 42 ,pages= {35--44} ,keywords= {graph color tabu} ,classif= {Coloring--Annealing/Tabu} ) @book( fiwi77 ,editor= {Stanley Fiorini and Robin J. Wilson} ,title= {Edge-Colourings of Graphs} ,publisher= {Pitman} ,address= {London} ,year= 1977 ,series= {Pitman Research Notes in Mathematics} ,volume= 16 ,keywords= {graph color} ,classif= {MATH LIB QA612.18 F52 1977} ) @incollection( fiwi78 ,author= {Stanley Fiorini and Robin J. Wilson} ,title= {Edge-Colourings of Graphs} ,booktitle= {Selected Topics in Graph Theory} ,chapter= 5 ,publisher= ap ,year= 1978 ,editor= {Lowell W. Beineke and Robin J. Wilson} ,pages= {103--126} ,address= {London} ,keywords= {edge coloring} ,classif= {Edge Coloring} ) @incollection( for71 ,author= {J. A. Formby} ,title= {A Computer Procedure for Bounding the Chromatic Number of a Graph} ,booktitle= {Combinatorial Mathematics and its Applications (Proceedings of a Conference held at the Mathematical Institute, Oxford, July, 1969)} ,year= 1971 ,editor= {D. J. A. Welsh} ,pages= {111--114} ,publisher= ap ,address= {London} ,keywords= {graph coloring algorithms} ) @article( fre82 ,author= {E. C. Freuder} ,title= {A Sufficient Condition of Backtrack-Free Search} ,journal= jacm ,year= 1982 ,volume= 29 ,number= 1 ,pages= {24--32} ,keywords= {graph coloring related algorithms} ) @incollection( fri90a ,author= {Alan M. Frieze} ,title= {Probabilistic Analysis of Graph Algorithms} ,booktitle= {Computational Graph Theory} ,year= 1990 ,editor= {G. Tinhofer and E. Mayr and H. Noltemeier} ,pages= {209--233} ,publisher= sv ,address= sva ,series= {Computing, Supplement} ,volume= 7 ,keywords= {graph coloring NP-completeness} ) @article( fri90b ,author= {Alan M. Frieze} ,title= {On the Independence Number of Random Graphs} ,journal= dm ,year= 1990 ,volume= 81 ,pages= {171--175} ,keywords= {graph coloring related clique} ) @incollection( frku90 ,author= {Alan M. Frieze and Lud\v{e}k Ku\v{c}era} ,title= {Parallel Colouring of Random Graphs} ,booktitle= {Random Graphs '87} ,year= 1990 ,editor= {M. Karo\'{n}ski and J. Jaworski and A. Ruci\'{n}ski} ,pages= {41--52} ,publisher= wiley ,keywords= {graph coloring } ,classif= {Planar/Parallel Coloring} ) @article( frlu92 ,author= {Alan M. Frieze and Tomasz {\L}uczak} ,title= {On the Independence and Chromatic Numbers of Random Regular Graphs} ,journal= jctsb ,year= 1992 ,volume= 54 ,pages= {123--132} ,keywords= {graph coloring random graphs chromatic number} ) @article( frs93 ,author= {T. A. Feo and M. G. C. Resende and S. H. Smith} ,title= {Greedy Randomized Adaptive Search Procedure for Maximum Independent Set} ,journal= {Operations Research} ,year= 1993 ,volume= {41} ,number= {} ,pages= {} ,keywords= {} ,classif= {Referenced in DIMACS Cliques and Colorings Bibliography. Needs to be looked for. Have looked for it in 1992 editions and Jan-Feb and Mar-Apr 1993.} ) @inproceedings( fusu92 ,author= {Martin F\"{u}rer and C. R. Subramanian} ,title= {Coloring Random Graphs} ,booktitle= {Algorithm Theory---SWAT '92, The Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July, 1992} ,editor= {O. Nurmi and E. Ukkonen} ,year= 1992 ,series= lncs ,volume= 621 ,pages= {284--291} ,keywords= {graph coloring random} ,classif= {Hard and Easy Coloring} ) @article( gajo75 ,author= {Michael R. Garey and David S. Johnson} ,title= {A Letter on the {S}alazar and {O}akford Paper [saoa74]} ,journal= cacm ,year= 1975 ,volume= 18 ,number= 4 ,month= apr ,pages= {240--241} ,keywords= {graph coloring} ,annote= {This letter disutes the claim by Salazar and Oakford that the size of the largest complete subraph plus 1 is an upper bound on the chromatic number. It also suggests that Salazar and Oakford's approximate algorithm will {\em rarely} find the largest complete subgraph for most graphs which arise in practice.} ) @article( gajo76 ,author= {Michael R. Garey and David S. Johnson} ,title= {The Complexity of Near-Optimal Graph Coloring} ,journal= jacm ,year= 1976 ,volume= 23 ,number= 1 ,month= jan ,pages= {43--49} ,keywords= {graph color heuristic algorithm complexity} ,classif= {Coloring--Complexity Results} ) @article( gaka82 ,author= {Harold N. Gabow and Oded Kariv} ,title= { Algorithms for Edge Coloring Bipartite Graphs and Multigraphs} ,journal= sicomp ,year= 1982 ,volume= 11 ,number= 1 ,pages= {117--129} ,mrnumbers= { 83g#68098} ,classif= {Edge Coloring} ) @article( gav72 ,author= {F\u{a}nic\u{a} Gavril} ,title= {Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph} ,journal= sicomp ,year= 1972 ,volume= 1 ,number= 2 ,pages= {180--187} ,month= jun ,keywords= {chordal graph coloring clique independent set R-orientation} ,classif= {Cliques and Independent Sets} ) @article( geli79 ,author= {L. Gerhards and W. Lindenberg} ,title= {Clique Detection for Nondirected Graphs: Two New Algorithms} ,journal= comp ,volume= 21 ,year= 1979 ,pages= {295--322} ,keywords= {graph coloring related not too good} ,classif= {Cliquess and Independent Sets} ) @article( gio87 ,author= { Gionfriddo, Mario} ,title= {A Short Survey of Some Generalized Colourings of Graphs} ,journal= arsco ,year= 1987 ,volume= 24 ,number= {B} ,pages= {155--163} ,keywords= {graph color algorithm} ,mrnumbers= { 89c#05036} ,classif= {Generalized Coloring} ) @article( gjmp80 ,author= {Michael R. Garey and David S. Johnson and G. L. Miller and Christos H. Papadimitriou} ,title= {The Complexity of Coloring Circular Arcs and Chords} ,journal= sijadm ,year= 1980 ,volume= 1 ,number= 2 ,pages= {216--227} ,month= jun ,keywords= {graph coloring} ) @article( gjs76b ,author= {Michael R. Garey and David S. Johnson and L. Stockmeyer} ,title= {Some Simplified {{\em NP}}-Complete Graph Problems} ,journal= tcs ,year= 1976 ,volume= 1 ,pages= {237--267} ,classif= {Coloring--Complexity Results} ) @article( gjs76a ,author= {Michael R. Garey and David S. Johnson and Hing C. So} ,title= {An Application of Graph Coloring to Printed Circuit Testing} ,journal= {IEEE Transactions on Circuits and Systems} ,year= 1976 ,volume= {Vol. CAS-23} ,number= 10 ,pages= {591--598} ,month= oct ,keywords= {graph coloring} ) @article( glo86 ,author= {Fred Glover} ,title= {Future Paths for Integer Programming and Links to Artificial Intelligence} ,journal= cor ,year= 1986 ,volume= 13 ,pages= {533--549} ,keywords= {tabu search} ) @article( glo89 ,author= {Fred Glover} ,title= {Tabu Search--{Part I}} ,journal= {ORSA Journal on Computing} ,year= 1989 ,volume= 1 ,number= 3 ,pages= {190--206} ,keywords= {graph coloring tabu} ) @article( gls81 ,author= {M. Gr\"{o}tschel and L. Lov\'{a}sz and A. Schrijver} ,title= {The Ellipsoid Method and its Consequences in Combinatorial Optimization} ,journal= comb ,year= 1981 ,volume= 1 ,number= 2 ,pages= {169--197} ,keywords= {chromatic number combinatorial optimization} ) @article( goba65 ,author= {S. W. Golomb and L. D. Baumert} ,title= {Backtrack Programming} ,journal= jacm ,year= 1965 ,volume= 12 ,pages= {516--524} ,keywords= {graph coloring related algorithm} ) @article( gopl87 ,author= {Andrew V. Goldberg and Serge A. Plotkin} ,title= {Parallel {$(\Delta + 1)$}-Coloring of Constant-Degree Graphs} ,journal= ipl ,year= 1987 ,volume= 25 ,number= 4 ,pages= {241--245} ,month= jun ,keywords= {parallel algorithm graph coloring maximal independent set} ) @article( gri83 ,author= {Jerrold R. Griggs} ,title= {Lower bounds on the Independence Number in Terms of the Degrees} ,journal= jctsb ,year= 1983 ,volume= 34 ,pages= {22--39} ,keywords= {graph coloring related clique theory} ) @article( grmc75 ,author= {G. R. Grimmett and C. J. H. McDiarmid} ,title= {On Colouring Random Graphs} ,journal= mpcps ,year= 1975 ,volume= 77 ,pages= {313--324} ,keywords= {graph color} ,mrnumbers= {51#5365} ,classif= {Random Graphs and Chromatic Number} ) @article( gru70 ,author= {B. Gr\"{u}nbaum} ,title= {A Problem in Graph Coloring} ,journal= amm ,year= 1970 ,volume= 77 ,pages= {1088-1092} ,keywords= {graph coloring theory girth false conjecture} ) @techreport( gya85 ,author= {Andr\'{a}s Gy\'{a}rf\'{a}s} ,title= {Problems from the World Surrounding Perfect Graphs} ,institution= {Computer and Automation Institute Studies} ,year= 1985 ,type= resrep ,number= {177} ,keywords= {graph coloring} ) @article( gyle88 ,author= {Andr\'{a}s Gy\'{a}rf\'{a}s and Jen\"{o} Lehel} ,title= {On-Line and First Fit Colorings of Graphs} ,journal= jgt ,year= 1988 ,volume= 12 ,number= 2 ,pages= {217--227} ,keywords= {graph color algorithm} ,mrnumbers= {89c#05037} ,classif= {On-Line Coloring} ) @article( gyle91 ,author= {Andr\'{a}s Gy\'{a}rf\'{a}s and Jen\"{o} Lehel} ,title= {Effective On-Line Coloring of {$P_5$}-Free Graphs} ,journal= comb ,year= 1991 ,volume= 11 ,number= 2 ,pages= {181--184} ,keywords= {graph coloring related algorithms} ) @article( hade78 ,author= {P. Hansen and M. Delattre} ,title= {Complete-Link Cluster Analysis by Graph Coloring} ,journal= {Journal of the American Statistical Society} ,year= 1978 ,volume= 73 ,pages= {397--403} ,keywords= {graph coloring application} ) @article( haku90 ,author= {Pierre Hansen and Julio Kuplinsky} ,title= {Slightly Hard-to-Color Graphs} ,journal= {Congressus Numerantium} ,year= 1990 ,volume= 78 ,pages= {81--98} ,keywords= {graph coloring} ) @article( hal80 ,author= {William K. Hale} ,title= {Frequency Assignment: Theory and Applications} ,journal= {Proceedings of the IEEE} ,year= 1980 ,volume= 68 ,number= 12 ,pages= {1497--1514} ,month= dec ,keywords= {graph coloring chromatic number} ) @phdthesis( hal91 ,author= {Magn\'{u}s M. Halld\'{o}rsson} ,title= {Frugal Methods for the Independent Set and Graph Coloring Problems} ,school= {Rutgers the State University of New Jersey} ,year= 1991 ) @inproceedings( hal92 ,author= {Magn\'{u}s M. Halld\'{o}rsson} ,title= {Parallel and On-Line Graph Coloring Algorithms} ,booktitle= {ISAAC '92 The Third Annual International Symposium on Algorithms and Computation} ,year= 1992 ,organization= {Nagoya University} ,classif= {Planar/Parallel Coloring} ) @incollection( hasz92 ,author= {Magn\'{u}s M. Halld\'{o}rsson and M\'{a}ri\'{o} Szegedy} ,title= {Lower Bounds for On-Line Graph Coloring} ,booktitle= {On-line Algorithms (New Brunswick, NJ, 1991)} ,series= dimacs ,publisher= {American Mathematical Society} ,address= {Providence, RI} ,year= 1992 ,volume= 7 ) @article( hcd89 ,author= {Torben Hagerup and Marek Chrobak and Krzysztof Diks} ,title= {Optimal Parallel $5$-Colouring of Planar Graphs} ,journal= sicomp ,year= 1989 ,volume= 18 ,number= 2 ,pages= {288--300} ,month= apr ,keywords= {planar graph coloring parallel algorithm} ) @article( hea90 ,author= {P. J. Heawood} ,title= {Map Colour Theorem} ,journal= {Quarterly Journal of Pure and Applied Mathematics} ,year= 1890 ,volume= 24 ,pages= {332--338} ,keywords= {graph coloring related theory} ,annote= {This is an early article on the map coloring problem.} ) @article( hed85 ,author= {Bruce Hedman} ,title= {The Maximum Number of Cliques in Dense Graphs} ,journal= dm ,year= 1985 ,volume= 54 ,number= 2 ,pages= {161--166} ,keywords= {graph coloring related clique theory} ,classif= {Cliques and Independent Sets} ) @incollection( heki81 ,author= {P. Hell and D. G. Kirkpatrick} ,title= { Scheduling, Matching, and Coloring} ,booktitle= {Algebraic Methods in Graph Theory, Vol. I, II} ,publisher= nh ,year= 1981 ,pages= {273--279} ,series= { Colloq. Math. Soc. Janos Bolyai, 25} ,mrnumbers= {83c#68074} ) @article( her90 ,author= {A. Hertz} ,title= {A Fast Algorithm for Coloring Meyniel Graphs} ,journal= jctsb ,year= 1990 ,volume= 50 ,pages= {231--240} ,keywords= {graph coloring maximum clique} ) @article( hewe87 ,author= {A. Hertz and D. de Werra} ,title= { Using Tabu Search Techniques for Graph Coloring} ,journal= comp ,year= 1987 ,volume= 39 ,number= 4 ,pages= {345--351} ,keywords= {graph color algorithm tabu} ,mrnumbers= { 88m#05038} ,classif= {Coloring--Annealing/Tabu} ) @article( hewe89 ,author= {A. Hertz and D. de Werra} ,title= {Connected Sequential Colorings} ,journal= dm ,year= 1989 ,volume= 74 ,number= {1-2} ,pages= {51--59} ,keywords= {graph coloring} ) @inproceedings( hiwi89 ,author= {A. J. W. Hilton and Robin J. Wilson} ,title= {Edge Colorings of Graphs: A Progress Report} ,booktitle= {Graph Theory and its Applications East and West: Proceedings of the First China-USA International Graph Theory Conference} ,year= 1989 ,pages= {241--249} ,series= nyas ,volume= 576 ,keywords= {graph coloring related theory survey} ,classif= {Edge Coloring} ) @article( hoe88 ,author= {Cornelis Hoede} ,title= {Hard Graphs for the Maximum Clique Problem} ,journal= dm ,year= 1988 ,volume= 72 ,number= {1--3} ,pages= {175--179} ,keywords= {graph coloring related clique theory} ,classif= {Cliques and Independent Sets} ) @article( hol69 ,author= {P. Holgate} ,title= {Majorants of the Chromatic Number of a Random Graph} ,journal= {J. Roy. Statist. Soc. Ser. B.} ,year= 1969 ,volume= 31 ,pages= {303--309} ,keywords= {graph color} ) @article( hol81 ,author= {Ian Holyer} ,title= {The {NP}-Completeness of Edge-Coloring} ,journal= sicomp ,year= 1981 ,volume= 10 ,number= 4 ,pages= {718--720} ,month= nov ,keywords= {edge coloring} ) @article( hole88 ,author= {Chin-Wen Ho and Richard C. T. Lee} ,title= {Efficient Parallel Algorithms for Finding Maximal Cliques, Clique Trees, and Minimum Coloring on Chordal Graphs} ,journal= ipl ,year= 1988 ,volume= 28 ,number= 6 ,pages= {301--309} ,month= aug ,keywords= {maximum cliques graph coloring parallel algorithm} ) @article( host85 ,author= {Glenn Hopkins and William Staton} ,title= {Graphs with Unique Maximum Independent Sets} ,journal= dm ,year= 1985 ,volume= 57 ,number= 3 ,pages= {245--251} ,keywords= {graph coloring related clique theory} ,classif= {Cliques and Independent Sets} ) @misc( hpv92 ,author= {Jonas Hasselberg and Panos M. Pardalos and George Vairaktarakis} ,key= {hpv92} ,title= {Test Case Generators and Computational Results for the Maximum Clique Problem} ,howpublished= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ,address= {University of Florida} ,year= 1992 ,note= {Working Paper} ) @article( hrs73 ,author= {A. J. W. Hilton and R. Rado and S. H. Scott} ,title= {A $(<5)$-Color Theorem for Planar Graphs} ,journal= {Bull. London Math. Soc.} ,year= 1973 ,volume= 5 ,pages= {302--306} ,note= {NCPY} ,keywords= {graph coloring chromatic number} ) @techreport( hsr91 ,author= {H. B. Hunt III and R. E. Stearns and S. S. Ravi} ,title= {Generalized Predicate Sets, Structure Trees, and Graph and Hypergraph Coloring Problems} ,institution= {Department of Computer Science, University at Albany, SUNY} ,year= 1991 ,type= techrep ,number= {TR 91-7} ,keywords= {abstract generalized coloring} ,classif= {Generalized Coloring} ) @incollection( ira90 ,author= {Sandy Irani} ,title= {Coloring Inductive Graphs On-Line} ,booktitle= focs90 ,year= 1990 ,pages= {470--479} ,publisher= {IEEE Computer Society Press} ,address= {Los Alamitos, CA} ,keywords= {graph coloring related theory} ,classif= {On-Line Coloring} ) @inproceedings( jag92 ,author= {Arun Jagota} ,title= {Efficiently Approximating {\em {M}ax-{C}lique} in a {H}opfield-style Network} ,booktitle= {Proceedings of 1992 IEEE/INNS International Joint Conference on Neural Networks, Volume 2} ,year= 1992 ,pages= {248--253} ,note= {Also available from ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @article( jams91 ,author= {David S. Johnson and Cecilia R. Aragon and Lyle A. McGeoch and Catherine Schevon} ,title= {Optimization by Simulated Annealing: An Experimental Evaluation; Part {II}, Graph Coloring and Number Partitioning} ,journal= {Operations Research} ,year= 1991 ,volume= 39 ,number= 3 ,pages= {378--406} ,month= {May-June} ,keywords= {graph coloring randomized} ,classif= {Coloring--Annealing/Tabu} ) @techreport( jare92 ,author= {Arun Jagota and Kenneth W. Regan} ,title= {Performance of {MAX-CLIQUE} Approximation Heuristics Under Description-Length Weighted Distributions} ,institution= {State University at New York at Buffalo, Department of Computer Science} ,year= 1992 ,address= {226 Bell Hall, UB North Campus, Buffalo, NY, 14260-2000} ,note= {ftp ftp.cs.buffalo.edu users/jagota or ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @article( jer92 ,author= {Mark Jerrum} ,title= {Large Cliques Elude the {M}etropolis Process} ,journal= {Random Structures and Algorithms} ,year= 1992 ,volume= 3 ,number= 4 ,pages= {347--359} ,keywords= {maximum clique algorithm} ) @article( joh74a ,author= {David S. Johnson} ,title= {Approximation Algorithms for Combinatorial Problems} ,journal= jcss ,year= 1974 ,volume= 9 ,pages= {256--278} ,keywords= {graph coloring heuristic algorithms} ,classif= {Coloring--Special Graphs/Antigraphs} ) @incollection( joh74b ,author= {David S. Johnson} ,title= {Worst Case Behavior of Graph Coloring Algorithms} ,booktitle= {Proceedings of 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing} ,year= 1974 ,pages= {513--527} ,publisher= {Utilitas Mathematica} ,address= {Winnipeg} ,keywords= {graph color} ,classif= {Coloring--Special Graphs/Antigraphs} ) @article( joh83 ,author= {David S. Johnson} ,title= {The {NP}-Completeness Column: An Ongoing Guide} ,journal= joa ,year= 1983 ,volume= 4 ,number= 2 ,pages= {189--203} ,keywords= {NP-completeness} ) @article( joh85 ,author= {David S. Johnson} ,title= {The {NP}-Completeness Column: An Ongoing Guide} ,journal= joa ,year= 1985 ,volume= 6 ,number= 3 ,pages= {434--451} ,keywords= {NP-completeness} ) @article( joh92 ,author= {David S. Johnson} ,title= {The {NP}-Completeness Column: An Ongoing Guide} ,journal= joa ,year= 1992 ,volume= 13 ,pages= {502--524} ,keywords= {NP-completeness} ,annote= {This is the 23rd edition of an irregularly appearing column that covers new developments in the theory of NP-completeness. Background material for it can be found in the book by Johnson and Garey, ``Computers and Intractability: A Guide to the Theory of NP-Completeness,'' W. H. Freeman & Co., NY, 1979. Any researchers wishing to send comments or suggestions or to submit papers for future editions should send them to David S. Johnson, Room 2D-150, AT&T Bell Laboratories, Murray Hill, NJ, 07974. For more details, see the December 1981 issue of the Journal of Algorithms.} ) @techreport( joma82 ,author= {Abhai Johri and David W. Matula} ,title= {Probabilistic Bounds and Heuristic Algorithms for Coloring Large Random Graphs} ,institution= {Department of Computer Science and Engineering, Southern Methodist University} ,address= {Dallas, Texas, 75275} ,month= jun ,year= 1982 ,type= techrep ,number= {82-CSE-06} ,keywords= {graph color algorithms} ,classif= {Heuristic Coloring} ) @inproceedings( josa89 ,author= {Garry Johns and Farrokh Saba} ,title= {On the Path-Chromatic Number of a Graph} ,booktitle= {Graph Theory and its Applications East and West: Proceedings of the First China-USA International Graph Theory Conference } ,year= 1989 ,pages= {275--280} ,series= nyas ,volume= 576 ,keywords= {graph coloring generalization} ,classif= {Theoretical} ) @article( jyp88 ,author= {David S. Johnson and Mihalis Yannakakis and Christos H. Papadimitriou} ,title= {On generating All Maximal Independent Sets.} ,journal= ipl ,year= 1988 ,volume= 27 ,month= mar ,pages= {119--123} ,keywords= {graph color} ) @inproceedings( kan92 ,author= {Viggo Kann} ,title= {On the Approximability of the Maximum Common Subgraph Problem} ,booktitle= {STACS 92} ,year= 1992 ,pages= {377--388} ,keywords= {graph coloring related clique approximation complexity} ) @article( kana88 ,author= {Mauricio Karchmer and Joseph Naor} ,title= {A Fast Parallel Algorithm to Color a Graph with {$\Delta$} Colors} ,journal= joa ,year= 1988 ,volume= 9 ,number= 1 ,pages= {83--91} ,keywords= {parallel algorithm graph coloring} ) @incollection( kar72 ,author= {Richard M. Karp} ,title= {Reducibility Among Combinatorial Problems} ,booktitle= {Complexity of Computer Computations (Proceedings of a Symposium on the Complexity of Computer Computations, March, 1972, Yorktown Heights, NY)} ,publisher= {Plenum Press} ,address= {New York} ,year= 1972 ,editor= {Raymond E. Miller and James W. Thatcher} ,pages= {85--103} ,keywords= {graph coloring complexity} ) @article( kar89 ,author= {Howard J. Karloff} ,title= {An {NC} Algorithm for {B}rooks' Theorem} ,journal= tcs ,year= 1989 ,volume= 68 ,number= 1 ,pages= {89--103} ,keywords= {} ,mrnumbers= {91d68050} ,classif= {Have sent for this through interlibrary loan.} ) @article( keke54 ,author= {J. B. Kelly and L. M. Kelly} ,title= {Paths and Circuits in Critical Graphs} ,journal= {American Journal of Mathematics} ,year= 1954 ,volume= 76 ,pages= {786--792} ,note= {theory graph coloring} ) @article( kem79 ,author= {A. B. Kempe} ,title= {On the Geographical Problem of the Four Colours} ,journal= {American Journal of Mathematics} ,year= 1879 ,volume= 2 ,pages= {193--201} ,keywords= {map coloring four color problem} ,annote= {This is an early paper on the graph coloring problem.} ) @article( kgv83 ,author= {S. Kirkpatrick and C. D. Gelatt\ Jr. and M. P. Vecchi} ,title= {Optimization by Simulated Annealing} ,journal= {Science} ,year= 1983 ,volume= 220 ,number= 4598 ,pages= {671--679} ,month= may ,keywords= {graph coloring} ,classif= {Coloring--Annealing/Tabu} ) @article( khe88 ,author= {E. M. Kheifets} ,title= { Planning of Operation of Communications Links in Packet Radio Networks, Using a Graph-Coloring Algorithm} ,journal= accs ,year= 1988 ,volume= 22 ,number= 5 ,pages= {34--37} ) @article( khu90a ,author= {Samir Khuller} ,title= {Coloring Algorithms for {$K_5$}-Minor Free Graphs} ,journal= ipl ,year= 1990 ,volume= 34 ,month= apr ,pages= {203--208} ,keywords= {graph color} ,classif= {Planar/Parallel Coloring} ) @article( khu90b ,author= {Samir Khuller} ,title= {Extending Planar Graph Algorithms to {$K_{3,3}$}-Free Graphs} ,journal= iac ,year= 1990 ,volume= 84 ,number= 1 ,pages= {13--25} ,keywords= {graph color} ,mrnumbers= { 91c#68052} ,classif= {Planar/Parallel Coloring} ) @article( khva89 ,author= {Samir Khuller and Vijay V. Vazirani} ,title= {Planar Graph Coloring is Not Self-Reducible Assuming {P} $\neq$ {NP}} ,journal= tcs ,year= 1991 ,volume= 88 ,pages= {183--189} ,keywords= {graph color} ) @incollection( kitr92 ,author= {H. A. Kierstead and W. T. Trotter} ,title= {On-Line Graph Coloring} ,booktitle= {On-line Algorithms (New Brunswick, NJ, 1991)} ,series= dimacs ,publisher= {American Mathematical Society} ,address= {Providence, RI} ,year= 1992 ,volume= 7 ) @article( knn82 ,author= {Tsuyoshi Kawaguchi and Hideo Nakano and Yoshiro Nakanishi} ,title= { Probabilistic Analysis of a Heuristic Graph Coloring Algorithm} ,journal= { Electronics and Communications in Japan} ,year= 1982 ,volume= {Vol. 65-A} ,number= 6 ,pages= {12--18} ,mrnumbers= {85e#05146} ) @article( koma75 ,author= {Robert R. Korfhage and David W. Matula} ,title= {A Letter on the {S}alazar and {O}akford Paper [saoa74]} ,journal= cacm ,year= 1975 ,volume= 18 ,number= 4 ,pages= {240} ,month= apr ,keywords= {graph coloring} ,annote= {This is a discussion of the upper bound of the chromatic number of a graph. It disputes the claim by Salazar and Oakford that the size of the largest complete subraph plus 1 is an upper bound on the chromatic number. It points out that {\em CWMAX is} an upper bound on the chromatic number.} ) @incollection( kor79 ,author= {Samuel M. Korman} ,title= {The Graph-Colouring Problem} ,booktitle= {Combinatorial Optimization} ,publisher= wiley ,address= {New York} ,year= 1979 ,editor= {Nicos Christofides and Aristide Mingozzi and Paolo Toth and Claudio Sandi} ,pages= {211--235} ,keywords= {graph color exact algorithms} ) @article( kor80 ,author= {A. D. Korshunov} ,title= {The Chromatic Number of $n$-Vertex Graphs} ,journal= {Diskret. Analiz} ,year= 1980 ,volume= 35 ,pages= {15--44} ,note= {in Russian} ,keywords= {graph color} ) @incollection( kppsz92 ,author= {Zvi M. Kedem and Krishna V. Palem and Grammati E. Pantziou and Paul G. Spirakis and Christos D. Zaroliagis} ,title= {Fast Parallel Algorithms for Coloring Random Graphs} ,booktitle= {Graph-Theoretic Concepts in Computer Science (Proceedings of the 17th International Workshop, WG '91, Fischbachau, Germany, June, 1991)} ,year= 1992 ,editor= {G. Schmidt and R. Berghammer} ,pages= {135--147} ,publisher= sv ,address= sva ,series= lncs ,volume= 570 ,keywords= {parallel algorithms graph coloring random graphs} ) @incollection (kro72 ,author= {Hudson V. Kronk} ,booktitle= {Graph Theory and Applications (Proceedings of the Conference at Western Michigan University, May, 1972)} ,title= {The Chromatic Number of Triangle-Free Graphs} ,series= lnm ,editor= {Y. Alavi and D. R. Lick and A. T. White} ,pages= {179--181} ,volume= 303 ,publisher= sv ,address= sva ,year= 1972 ,keywords= {graph coloring theory girth} ) @incollection( krr89 ,author= {N. K. Karmarkar and K. G. Ramakrishnan and M. G. C. Resende} ,title= {An Interior Point Approach to the Maximum Independent Set Problem in Dense Random Graphs} ,booktitle= {Proceedings of the XV Latin American Conference on Informatics I} ,publisher= {} ,year= 1989 ,editor= {} ,pages= {241--260} ,address= {} ,keywords= {} ,classif= {Referenced in DIMACS Cliques and Colorings Bibliography. Have sent for it through interlibrary loan.} ) @article( krwh72 ,author= {Hudson V. Kronk and A. T. White} ,title= {A 4-color Theorem for Toroidal Graphs} ,journal= pams ,year= 1972 ,volume= 34 ,pages= {83--86} ,keywords= {graph coloring related theory} ) @article( kub87 ,author= {Marek Kubale} ,title= {Interval Edge-Coloring of Caterpillars with Hairs of Arbitrary Lengths} ,journal= {Zastosowania Mathematyki Applicationes Mathematicae} ,year= 1987 ,volume= 19 ,number= {3-4} ,pages= {505-517} ,keywords= {generalized graph coloring} ,classif= {Generalized Coloring} ) @article( kub89 ,author= {Marek Kubale} ,title= {Interval Vertex-Coloring of a Graph with Forbidden Colors} ,journal= dm ,year= 1989 ,volume= 74 ,pages= {125--136} ,keywords= {generalized graph coloring} ,classif= {Generalized Coloring} ) @incollection( kub91 ,author= {Marek Kubale} ,editor= {Allen Kent and James G. Williams} ,booktitle= {Encyclopedia of Microcomputers} ,title= {Graph Coloring} ,pages= {47--69} ,publisher= {Marcel Dekker, Inc.} ,year= 1991 ,volume= 8 ,address= {New York} ,keywords= {survey of graph coloring} ,annote= {This is a survey of graph coloring.} ,classif= {Approximate Algorithms--Worst Case Guarantees} ) @article( kub92 ,author= {Marek Kubale} ,title= {Some Results Concerning the Complexity of Restricted Colorings of Graphs} ,journal= dam ,year= 1992 ,volume= 36 ,pages= {35--46} ,keywords= {generalized graph coloring chromatic index chromatic number NP-completeness} ,classif= {Generalized Coloring} ) @incollection( kuc77 ,author= {L. Ku\v{c}era} ,editor= {Marek Karpi\'{n}ski} ,title= {Expected Behavior of Graph Coloring Algorithms} ,booktitle= {Fundamentals of Computation Theory (Proceedings of the 1977 FCT-Conference, Pozna\'{n}-K\'{o}rnik, Poland, Sept, 1977)} ,publisher= sv ,year= 1977 ,pages= {447--451} ,address= sva ,keywords= {graph color} ,series= lncs ,volume= 56 ) @article( kuc89 ,author= {Lud\v{e}k Ku\v{c}era} ,title= {Graphs with Small Chromatic Numbers are Easy to Color} ,journal= ipl ,year= 1989 ,volume= 30 ,number= 5 ,pages= {233--236} ,keywords= {graph color} ,classif= {Hard and Easy Coloring} ) @article( kuc91 ,author= {Lud\v{e}k Ku\v{c}era} ,title= {The Greedy Coloring is a Bad Probabilistic Algorithm} ,journal= joa ,year= 1991 ,volume= 12 ,pages= {674--684} ,keywords= {graph coloring greedy algorithm} ) @incollection( kuc92 ,author= {Lud\v{e}k Ku\v{c}era} ,title= {A Generalized Encryption Scheme Based on Random Graphs} ,booktitle= {Graph-Theoretic Concepts in Computer Science (Proceedings of the 17th International Workshop, WG '91, Fischbachau, Germany, June, 1991)} ,year= 1992 ,editor= {G. Schmidt and R. Berghammer} ,publisher= sv ,pages= {180--186} ,address= sva ,keywords= {hiding independent sets } ,series= lncs ,volume= 570 ) @article( kuja85 ,author= {Marek Kubale and Boguslaw Jackowski} ,title= { A Generalized Implicit Enumeration Algorithm for Graph Coloring} ,journal= cacm ,year= 1985 ,volume= 28 ,number= 4 ,pages= {412--418} ,month= apr ,classif= {Coloring Algorithms--Exact} ) @incollection( kuku83 ,author= {Marek Kubale and E. Kusz} ,title= {Computer Experiences with Implicit Enumeration Algorithms for Graph Coloring} ,booktitle= {Graphtheoretic Concepts in Computer Science (Proceedings of the 9th International Workshop, WG '83, Linz, Austria)} ,year= 1983 ,editor= {M. Nagl and J. Perl} ,pages= {167--176} ,publisher= {Trauner Verlag} ,keywords= {graph coloring algorithm complexity} ) @article( law76 ,author= {E. L. Lawler} ,title= {A Note on the Complexity of the Chromatic Number Problem} ,journal= ipl ,year= 1976 ,volume= 5 ,number= 3 ,month= aug ,pages= {66--67} ,keywords= {graph color} ) @article( lei79 ,author= {Frank Thomson Leighton} ,title= {A Graph Colouring Algorithm for Large Scheduling Problems} ,journal= {Journal of Research of the National Bureau of Standards} ,year= 1979 ,volume= 84 ,number= 6 ,pages= {489--503} ,keywords= {graph color heuristic algorithm} ) @article( lin86 ,author= {Nathan Linial} ,title= {Graph Coloring and Monotone Functions on Posets} ,journal= dm ,year= 1986 ,volume= 58 ,number= 1 ,pages= {97--98} ,mrnumbers= { 87d#05078} ) @article( lita79 ,author= {Richard Lipton and Robert Tarjan} ,title= {A Separator Theorem for Planar Graphs} ,journal= sijam ,year= 1979 ,volume= 36 ,pages= {346--358} ,keywords= {graph coloring related clique approximation} ) @article( lita80 ,author= {Richard Lipton and Robert Tarjan} ,title= {Applications of a Planar Separator Theorem} ,journal= sicomp ,year= 1980 ,volume= 9 ,number= 3 ,pages= {615--626} ,keywords= {graph coloring related topics clique approximation} ) @incollection( liva89 ,author= {Nati Linial and Umesh Vazirani} ,title= {Graph Products and Chromatic Numbers} ,booktitle= focs89 ,year= 1989 ,pages= {124--128} ,publisher= {IEEE Computer Society Press} ,address= {Los Alamitos, CA} ,keywords= {graph coloring theory} ) @article( losa86 ,author= { Lotfi, Vahid and Sarin, Sanjiv} ,title= { A Graph Coloring Algorithm for Large Scale Scheduling Problems} ,journal= cor ,year= 1986 ,volume= 13 ,number= 1 ,pages= {27--32} ,mrnumbers= { 87e#90052} ,keywords= {graph coloring heuristic algorithm scheduling} ,classif= {Coloring Algorithms--Heuristic} ) @article( lots82 ,author= {E. Loukakis and C. Tsouros} ,title= {Determining the Number of Internal Stability of a Graph} ,journal= ijcm ,year= 1982 ,volume= 11 ,pages= {207--220} ,keywords= {algorithm for the independent set of a graph} ,classif= {Cliques and Independent Sets} ) @article( lou83 ,author= {E. Loukakis} ,title= {A New Backtracking Algorithm for Generating the Family of Maximal Independent Sets of a Graph} ,journal= cmpmth ,year= 1983 ,volume= 9 ,pages= {583--589} ,keywords= {graph color} ) @article( lov66 ,author= {L\'{a}szl\'{o} Lov\'{a}sz} ,title= {On Decomposition of Graphs} ,journal= {Studia Sci. Math. Hungar.} ,year= 1966 ,volume= 1 ,pages= {237--238} ,keywords= {graph coloring related theory} ) @article( lov68 ,author= {L\'{a}szl\'{o} Lov\'{a}sz} ,title= {On the Chromatic Number of Finite Set Systems} ,journal= {Acto. Math. Acad. Sci. Hungary} ,year= 1968 ,volume= 19 ,pages= {59--67} ,keywords= {graph coloring} ) @article( lst89 ,author= {L\'{a}szl\'{o} Lov\'{a}sz and Michael Saks and W. T. Trotter } ,title= {An On-Line Graph Coloring Algorithm with Sublinear Performance Ratio} ,journal= dm ,year= 1989 ,volume= 75 ,number= {1-3} ,pages= {319--325} ) @article( luc91a ,author= {Tomasz {\L}uczak} ,title= {The Chromatic Number of Random Graphs} ,journal= comb ,year= 1991 ,volume= 11 ,number= 1 ,pages= {45--54} ,keywords= {graph coloring random graph theory} ) @article( luc91b ,author= {Tomasz {\L}uczak} ,title= {A Note on the Sharp Concentration of the Chromatic Number of Random Graphs} ,journal= comb ,year= 1991 ,volume= 11 ,number= 3 ,pages= {295--297} ,keywords= {graph coloring} ) @article( luwi89 ,author= {Tomasz {\L}uczak and J. C. Wierman} ,title= {The Chromatic Number of Random Graphs at the Double-Jump Threshold} ,journal= comb ,year= 1989 ,volume= 9 ,number= 1 ,pages= {39--49} ,keywords= {graph coloring chromatic number} ) @inproceedings( luya93 ,author= {Carsten Lund and Mihalis Yannakakis} ,title= {On the Hardness of Approximating Minimization Problems} ,booktitle= stoc93 ,year= 1993 ,pages= {} ,keywords= {graph coloring} ) @article( mabe83 ,author= {David W. Matula and Leland L. Beck} ,title= { Smallest-Last Ordering and Clustering and Graph Coloring Algorithms} ,journal= jacm ,year= 1983 ,volume= 30 ,number= 3 ,month= jul ,pages= {417--427} ,classif= {Coloring Algorithms--Heuristic} ) @incollection( maku90 ,author= {David W. Matula and Lud\v{e}k Ku\v{c}era} ,title= {An Expose-and-Merge Algorithm and the Chromatic Number of a Random Graph} ,booktitle= {Random Graphs '87} ,year= 1990 ,editor= {M. Karo\'{n}ski and J. Jaworski and A. Ruci\'{n}ski} ,pages= {175--187} ,publisher= wiley ,address= {New York} ,keywords= {graph coloring random graph theory randomization} ,classif= {Random Graphs and Chromatic Number} ) @article( man81 ,author= {Bennet Manvel} ,title= {Coloring Large Graphs} ,journal= {Congressus Numerantium} ,volume= 33 ,year= 1981 ,pages= {197-204} ) @incollection( man85 ,author= {Bennet Manvel} ,editor= {Frank Harary and John S. Maybee} ,title= {Extremely Greedy Coloring Algorithms} ,booktitle= { Graphs and Applications (Proceedings of the First Colorado Symposium on Graph Theory, 1982)} ,year= 1985 ,pages= {257--270} ,publisher= wiley ,address= {New York} ,keywords= {graph color} ,mrnumbers= {86b#05033} ,classif= {Heuristic Coloring} ) @article( masa93 ,author= {Carlo Mannino and Antonio Sassano} ,title= {An Exact Algorithm for the Maximum Cardinality Stable Set Problem} ,journal= {Networks} ,year= 1993 ,pages= {(submitted)} ,note= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @article( mat68 ,author= {David W. Matula} ,title= {A Min-Max Theorem for Graphs with Application to Graph Coloring} ,journal= sirev ,year= 1968 ,volume= 10 ,pages= {481--482} ,keywords= {graph color} ) @article( mat72 ,author= {David W. Matula} ,title= {Bounded Color Functions on Graphs} ,journal= {Networks} ,year= 1972 ,volume= 2 ,pages= {29--44} ,keywords= {graph coloring} ) @article( mat87 ,author= {David W. Matula} ,title= { Expose-and-Merge Exploration and the Chromatic Number of a Random Graph} ,journal= comb ,year= 1987 ,volume= 7 ,number= 3 ,pages= {275--284} ,keywords= {graph color} ,mrnumbers= {89a#05121} ,classif= {Heuristic Coloring} ) @incollection( mata83 ,author= {A. Marchetti-{S}paccamela and M. Talamo} ,title= {Probabilistic Analysis of Graph Colouring Algorithms} ,booktitle= {Proceedings CAAP'83 (Trees in Algebra and Programming 8th Colloquium, L'Aquila, Mar, 1983)} ,year= 1983 ,editor= {G. Ausiello and M. Protasi} ,pages= {332--340} ,publisher= sv ,address= sva ,series= lncs ,volume= 159 ,keywords= {graph coloring algorithms chromatic number} ) @article( mcc83 ,author= {S. T. McCormick} ,title= {Optimal Approximation of Sparse {H}essians and its Equivalence to a Graph Coloring Problem} ,journal= matpgm ,year= 1983 ,volume= 26 ,number= 2 ,pages= {153--171} ) @incollection( mcd79a ,author= {Colin McDiarmid} ,title= { Colouring Random Graphs Badly} ,booktitle= {Graph theory and Combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978)} ,year= 1979 ,pages= {76--86} ,publisher= {Pitman} ,address= {San Francisco, CA} ,series= {Research Notes in Mathematics} ,volume= 34 ,keywords= {graph color} ,mrnumbers= { 82m#05045} ,classif= {Random Graphs and Chromatic Number} ) @article( mcd79b ,author= {Colin McDiarmid} ,title= {Determining the Chromatic Number of a Graph} ,journal= sicomp ,year= 1979 ,volume= 8 ,number= 1 ,month= feb ,pages= {1--14} ,keywords= {graph color} ) @article( mcd82 ,author= {Colin McDiarmid} ,title= {Achromatic Numbers of Random Graphs} ,journal= mpcps ,year= 1982 ,volume= 92 ,pages= {21--28} ,keywords= {graph color} ,classif= {Random Graphs and Chromatic Number} ) @article( mcd83 ,author= {Colin McDiarmid} ,title= {On the Chromatic Forcing Number of a Random Graph} ,journal= dam ,year= 1983 ,volume= 5 ,pages= {123--132} ,keywords= {graph color} ,classif= {Random Graphs and Chromatic Number} ) @article( mcd84 ,author= {Colin McDiarmid} ,title= {Colouring Random Graphs} ,journal= aor ,year= 1984 ,volume= 1 ,pages= {183--200} ,keywords= {graph color} ,classif= {Random Graphs and Chromatic Number} ) @article( mcd90 ,author= {Colin McDiarmid} ,title= {On the Chromatic Number of Random Graphs} ,journal= {Random Structures and Algorithms} ,year= 1990 ,volume= 1 ,number= 4 ,pages= {435--442} ,keywords= {graph coloring random graph theory} ,classif= {Random Graphs and Chromatic Number} ) @incollection( mil75 ,author= {D. Michael Miller} ,title= {An Algorithm for Determining the Chromatic Number of a Graph} ,booktitle= {Proceedings of the Fifth Manitoba Conference on Numerical Mathematics} ,series= {Congressus Numerantium} ,volume= {XVI} ,year= 1975 ,publisher= {Utilitas Mathematica} ,address= {Winnipeg} ,pages= {533--548} ,keywords= {graph color} ,classif= {Coloring Algorithms--Exact} ) @article( mit76 ,author= {John Mitchem} ,title= {On Various Algorithms for Estimating the Chromatic Number of a Graph} ,journal= tcj ,year= 1976 ,volume= 19 ,pages= {182--183} ,keywords= {graph color} ,classif= {Coloring--Special Graphs/Antigraphs} ) @incollection( mmi72 ,author= {David W. Matula and George Marble and Joel D. Isaacson} ,title= {Graph Coloring Algorithms} ,booktitle= {Graph Theory and Computing} ,publisher= ap ,editor= {R. C. Read} ,year= 1972 ,pages= {109--122} ,keywords= {graph color planar} ,mrnumbers= {50#4368} ,annote= {This paper presents experiments on random graphs up to 100 vertices using various ordering heuristics for sequential algorithms. Also included is a $5$-coloring algorithm for planar graphs.} ,classif= {Coloring Algorithms--Heuristic} ) @article( momo65 ,author= {J. W. Moon and L. Moser} ,title= {On Cliques in Graphs} ,journal= {Israel Journal of Mathematics} ,year= 1965 ,volume= 3 ,pages= {23--28} ,keywords= {graph coloring related topics special graphs} ,classif= {Cliques and Independent Sets} ) @phdthesis( mor89 ,author= {Craig A. Morgenstern} ,title= {Algorithms for General Graph Coloring} ,school= {Department of Computing Science, University of New Mexico} ,year= 1989 ,address= {Albuquerque, New Mexico} ,keywords= {graph coloring annealing} ) @incollection( mosh90 ,author= {Craig A. Morgenstern and Henry D. Shapiro} ,title= {Coloration Neighborhood Structures for General Graph Coloring} ,booktitle= {Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, Jan, 1990} ,year= 1990 ,pages= {226--235} ,publisher= {Society for Industrial and Applied Mathematics} ,address= {Philadelpia} ,keywords= {graph coloring algorithm} ) @article( mosh91 ,author= {Craig A. Morgenstern and Henry D. Shapiro} ,title= {Heuristics for Rapidly Four-Coloring Large Planar Graphs} ,journal= algo ,year= 1991 ,volume= 6 ,pages= {869--891} ,keywords= {graph coloring four coloring algorithm} ) @article( mosp85 ,author= {B. Monien and E. Speckenmeyer} ,title= {Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem} ,journal= acta ,year= 1985 ,volume= 22 ,pages= {115--123} ,note= {NCPY} ,keywords= {graph coloring} ) @article( muco72 ,author= {Gordon D. Mulligan and D. G. Corneil} ,title= {Corrections to {B}ierstone's Algorithm for Generating Cliques} ,journal= jacm ,year= 1972 ,volume= 19 ,number= 2 ,month= apr ,pages= {244--247} ,keywords= {graph coloring related topics} ) @article( myc55 ,author= {J. Mycielski} ,title= {Sur le Coloriage des Graphs} ,journal= {Colloquium Mathematicum} ,year= 1955 ,volume= 3 ,number= 2 ,pages= {161--162} ,keywords= {graph coloring} ) @article( nao87 ,author= {Joseph Naor} ,title= {A Fast Parallel Coloring of Planar Graphs with Five Colors} ,journal= ipl ,year= 1987 ,volume= 25 ,number= 1 ,month= apr ,pages= {51-53} ,keywords= {parallel algorithm planar graph coloring} ) @article( nera83 ,author= {Garry N. Newsam and John D. Ramsdell} ,title= { Estimation of Sparse {J}acobian Matrices} ,journal= sijadm ,year= 1983 ,volume= 4 ,number= 3 ,pages= {404--418} ,keywords= {graph color} ,mrnumbers= {84k#65058} ) @article( neta74 ,author= {G. A. Neufeld and J. Tartar} ,title= {Graph Coloring Conditions for the Existence of Solutions to the Timetable Problem} ,journal= cacm ,year= 1974 ,volume= 17 ,number= 8 ,pages= {450--453} ,month= aug ,classif= {Coloring Applications--Timetable} ) @article( neta75 ,author= {G. A. Neufeld and J. Tartar} ,title= {Generalized Graph Colorations} ,journal= sijam ,year= 1975 ,volume= 29 ,number= 1 ,month= jul ,pages= {91--98} ,keywords= {graph coloring} ) @article( netr75 ,author= {G. L. Nemhauser and Trotter, Jr., L. E.} ,title= {Vertex Packings: Structural Properties and Algorithms} ,journal= matpgm ,year= 1975 ,volume= 8 ,number= 2 ,pages= {232--248} ,keywords= {vertex packing algorithm} ) @book( newi90 ,editor= {Roy Nelson and Robin J. Wilson} ,title= {Graph Colourings} ,publisher= {Longman Scientific and Technical} ,address= {Harlow, Essex, UK} ,year= 1990 ,series= {Pitman Research Notes in Mathematics} ,volume= 218 ,keywords= {graph color} ) @article( nie74 ,author= {U. J. Nieminen} ,title= {A Viewpoint to the Minimum Coloring Problem of Hypergraphs} ,journal= {Kybernetika(Prague)} ,year= 1974 ,volume= 10 ,pages= {504--508} ,note= {MR vol. 51 p. 757} ,keywords= {graph coloring} ) @article( nil88 ,author= {A. Nilli} ,title= {The Average Size of an Independent Set in Graphs with a Given Chromatic Number (Note)} ,journal= jctsb ,year= 1988 ,volume= 45 ,pages= {112--114} ,keywords= {graph coloring independent set chromatic number} ) @article( obb81 ,author= {James B. Orlin and Maurizio A. Bonuccelli and Daniel P. Bovet} ,title= {An {$O(n^{2})$} Algorithm for Coloring Proper Circular Arc Graphs} ,journal= sijadm ,year= 1981 ,volume= 2 ,number= 2 ,pages= {88--93} ,month= jun ,keywords= {graph coloring algorithm} ) @article( ola88 ,author= {Stephan Olariu} ,title= {All Variations on Perfectly Orderable Graphs} ,journal= jctsb ,year= 1988 ,volume= 45 ,number= 2 ,pages= {150--159} ,keywords= {graph coloring related theory} ) @article( olra89 ,author= {Stephan Olariu and J. Randall} ,title= {Welsh-{P}owell Opposition Graphs} ,journal= ipl ,year= 1989 ,volume= 31 ,number= 1 ,month= apr ,pages= {43--46} ,keywords= {graph color orderable graphs} ,mrnumbers= { 90f#05118} ,classif= {Coloring--Special Graphs/Antigraphs} ) @incollection( opro81 ,author= {R. J. Opsut and F. S. Roberts} ,title= {On the Fleet Maintenance, Mobile Radio Frequency, Task Assignment, and Traffic Phasing Problems} ,booktitle= {The Theory and Applications of Graphs (Proceedings of the Fourth International Conference, May, 1980, Western Michigan University, Kalamazoo, Michigan)} ,year= 1981 ,editor= {G. Chartrand and Y. Alavi and D. L. Goldsmith and L. Lesniak-{F}oster and D. R. Lick} ,pages= {479--492} ,publisher= wiley ,address= {New York} ,keywords= {graph coloring applications chromatic number} ) @article( pade91 ,author= {Panos M. Pardalos and Nisha Desai} ,title= {An Algorithm for Finding a Maximum Weighted Independent Set in an Arbitrary Graph} ,journal= ijcm ,year= 1991 ,volume= 38 ,pages= {163--175} ,keywords= {graph coloring independent set slightly related} ,classif= {Cliques and Independent Sets} ) @article( paph90 ,author= {Panos M. Pardalos and A. T. Phillips} ,title= {A Global Optimization Approach for Solving the Maximum Clique Problem} ,journal= ijcm ,year= 1990 ,volume= 33 ,pages= {209--216} ,keywords= {graph coloring related algorithms clique} ,classif= {Cliques and Independent Sets} ) @article( paro92 ,author= {Panos M. Pardalos and Gregory P. Rodgers} ,title= {A Branch and Bound Algorithm for the Maximum Clique Problem} ,journal= cor ,year= 1992 ,volume= 19 ,number= 5 ,month= jul ,pages= {363--375} ,keywords= {graph coloring related clique} ,classif= {Cliques and Independent Sets} ) @inproceedings( pasr92 ,author= {Alessandro Panconesi and Aravind Srinivasan} ,title= {Improved Distributed Algorithms for Coloring and Network Decomposition Problems} ,booktitle= { Proceedings of the 24th Annual ACM Symposium on Theory of Computing} ,year= 1992 ,pages= {581--592} ,keywords= {graph coloring related algorithms} ,classif= {Planar/Parallel Coloring} ) @article( paxu93 ,author= {Panos M. Pardalos and Jue Xue} ,title= {The Maximum Clique Problem} ,journal= {Journal of Global Optimization} ,year= 1993 ,pages= {(to appear)} ,keywords= {maximum clique graph coloring algorithms heuristics bibliography} ,note= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ,mathrev= {A complete review of the clique problem} ,classif= {Cliques and Independent Sets} ) @inproceedings( paya88 ,author= {Christos H. Papadimitriou and Mihalis Yannakakis} ,title= {Optimization, Approximation and Complexity Classes (Extended Abstract)} ,booktitle= stoc88 ,year= 1988 ,pages= {229--234} ,keywords= {max snp theory } ) @article( pee83 ,author= {Peem\"{o}ller, Jurgen} ,title= {A Correction to {B}r\'{e}laz's Modification of {B}rown's Coloring Algorithm} ,journal= cacm ,year= 1983 ,volume= 26 ,number= 8 ,pages= {595--597} ,month= aug ,keywords= {graph color} ,classif= {Coloring Algorithms--Exact} ) @article( pee86 ,author= {Peem\"{o}ller, Jurgen} ,title= { Numerical Experiences with Graph Coloring Algorithms} ,journal= ejor ,year= 1986 ,volume= 24 ,number= 1 ,pages= {146--151} ,month= jan ,keywords= {graph color} ,mrnumbers= { 87h#0509} ,classif= {Heuristic Coloring} ) @article( pewe89 ,author= {A. D. Petford and D. J. A. Welsh} ,title= {A Randomised $3$-Colouring Algorithm} ,journal= dm ,year= 1989 ,volume= 74 ,pages= {253--261} ,keywords= {graph coloring algorithm} ) @article( pit82 ,author= {B. Pittel} ,title= {On the Probable Behaviour of Some Algorithms for Finding the Stability Number of a Graph} ,journal= mpcps ,year= 1982 ,volume= 92 ,pages= {511--526} ,keywords= {} ) @techreport( pro91 ,author= {Patrick Prosser} ,title= {Hybrid Algorithms for the Constraint Satisfaction Problem} ,institution= {University of Strathclyde, Department of Computer Science} ,year= 1991 ,type= resrep ,number= {AISL-46-91} ,address= {Livingstone Tower, 26 Richmond Street, Glasgow, G1 1XH, Scotland} ,month= sep ,keywords= {graph coloring related algorithms} ,classif= {Cliques and Independent Sets} ) @article( prsy86 ,author= {Andrzej Proskurowski and Maciej M. Sys{\l}o} ,title= {Efficient Vertex- and Edge-Coloring of Outerplanar Graphs} ,journal= sijadm ,year= 1986 ,volume= 7 ,number= 1 ,pages= {131--136} ,month= jan ,keywords= {graph coloring chromatic number chromatic index} ) @article( raj92 ,author= {Peter Raj\v{c}\'{a}ni} ,title= {Optimal Parallel 3-Coloring Algorithm for Rooted Trees and its Applications} ,journal= ipl ,year= 1992 ,volume= 41 ,number= 3 ,month= mar ,pages= {153--156} ,keywords= {parallel algorithm graph coloring} ) @techreport( ram91 ,author= {Rajeev Raman} ,title= {Generating Random Graphs Efficiently} ,institution= {University of Rochester, Computer Science Department} ,year= 1991 ,type= techrep ,number= 369 ,address= {Rochester, NY, 14627} ,month= jan ,keywords= {random directed and undirected graph generation} ) @incollection( rao79 ,author= {A. Ramachandra Rao} ,title= {The Clique Number of a Graph with a Given Degree Sequence} ,booktitle= {Proceedings of the Symposium on Graph Theory held at the Indian Statistical Institute, Dec, 1976} ,year= 1979 ,editor= {A. Ramachandra Rao} ,pages= {251--267} ,publisher= {MacMillan Company of India, Ltd} ,address= {Dehli, India} ,series= {Indian Statistical Institute Lecture Notes Series, No. 4} ,keywords= {maximum clique degree sequence} ) @article( riyo68 ,author= {G. Ringel and J. W. T. Youngs} ,title= {Solution of the {H}eawood Map Coloring Problem} ,journal= {Proceedings of the National Academy of Sciences U.S.A.} ,year= 1968 ,volume= 60 ,pages= {438--445} ,keywords= {graph coloring related theory} ) @article( rob71 ,author= {J. M. Robson} ,title= {An Estimate of the Store Size Necessary for Dynamic Storage Allocation} ,journal= jacm ,year= 1971 ,volume= 18 ,pages= {416--423} ,keywords= {related to online graph coloring} ) @article( rofu73 ,author= {S. I. Roschke and A. L. Furtado} ,title= {An Algorithm for Obtaining the Chromatic Number and An Optimal Coloring of a Graph} ,journal= ipl ,year= 1973 ,volume= 2 ,pages= {34--38} ,keywords= {graph coloring chromatic number algorithm} ) @incollection( rut86 ,author= {Vladislav Rutenberg} ,title= {Complexity of Generalized Graph Coloring} ,booktitle= {Mathematical Foundations of Computer Science 1986 (Proceedings of the Twelfth Symposium Held in Bratislava, Czechoslovakia)} ,editor= {J. Gruska and B. Rovan and J. Wiedermann} ,pages= {573--581} ,publisher= sv ,address= sva ,year= 1986 ,volume= 233 ,series= lncs ,classif= {Coloring--Complexity Results} ) @article( saba89 ,author= {S. Sen Sarma and S. K. Bandyopadhyay} ,title= {Some Sequential Graph Colouring Algorithms} ,journal= ije ,year= 1989 ,volume= 67 ,number= 2 ,pages= {187--199} ,keywords= {graph color} ,classif= {Coloring Algorithms--Heuristic} ) @article( saoa74 ,author= {A. Salazar and R. V. Oakford} ,title= {A Graph Formulation of a School Scheduling Algorithm} ,journal= cacm ,year= 1974 ,volume= 17 ,number= 12 ,month= dec ,pages= {696--698} ,keywords= {graph coloring scheduling timetable} ) @article( sco76 ,author= {Trevor B. Scott} ,title= {Graph Colouring with Preassignment and Unavailability Constraints} ,journal= arsco ,year= 1976 ,volume= 2 ,month= dec ,pages= {25--32} ,keywords= {graph coloring timetable} ) @incollection( scst74 ,author= {G. Schmidt and T. Str\"{o}hlein} ,title= {Some Aspects in the Construction of Timetables} ,booktitle= {Information Processing 7me= 7ce} ce} ccEdm Mathemurnal= curnal= cun Jaichael RinstitutioinstitutioiP}-P}-Pact}act}a91 91 9wedewedeww {aci B: B: oy forly} ly} lteened Coridauci\' Als Als the Cation Pation PaOpColoring ain 1Cliques, ournal= cacithm} , = {Ur Raong linOptimis H and Chr and Chr arallefth er} ,oloring}oloring}o--86oring }a Co,pages= {18icationuteuteu6} ,mon the {dge of Spobliquesrasrasromplublisublisuututenumb8}}id W.6} ,a6} ,a65} ,k5} ,k5r}ir}irnumbers= numbers= nn Computer Soc79 ,aut9 ,number=land}ybe} ,journal= {Af the Ite and J. and J. lassif= {ColoE. WmosbilecturectureeTrIGPIGPI sv ,oloring roloring roms}ionsperiperipplec} ,journal= }} @string{focs87vVoV. KV. KVen} lso0} ,pu {EvcDia Eces (atislly} imum C and E. Sthe C} ) @inprocypeypeyys' ,year= 1987 ,re}vingort( 7187187ooktiHon#5of an of an oer= {1al= tum} ,yum} ,yurin Jou5 ,vossachstring{gstring{gssASote=author= {B\author= {B\aukukuu ,volume= 75ies= ig ˜˜˜riezs ,yearrvey} ) @inp} ) @inp}ng relang relandm ,yelge Graphs} ,journal ,year= 1973Inst = {Iowel= {Zn Chwisversit6} ,mong} ,tg} ,tgloq= c} ) @article( h} ) @article( h}e mber= 4of Computingjanjanjd Td Td Proble5 ,numbe{PitWtin Atin Atts of the Twen, Je inde indeemontndrgacgacgof Computing} v Nv Nvloure Racocietycietyccepa1988Haroof Paof Paos, Gr} ,year= 1992 ,} ,year= 1992 ,}}uplupluity aity aiphs}dam} 3 ,pliffsj 7} ) R. GaR. GaRlgorithm uthor= {A.marcmarcminstis= {gsende81 ,p81 ,p8 \l, Vaticle(completecompleteclf}ions ora andentdentd Tebooktitle= {Grbooktitle= {Grbk} ,kV.NatNatNdings of rutgember} A. W, Teori81que, ichardenue Ra{\lshi. Mome Sng}} @strinaka71,y and y and ys, FrThi5 ,numberystemsystemsyS:Strator or o980 lemelemelum} ,yu ocdam}dam}ddo,euristic}4--1stem ,volume= 2 ,7} ,key,inin McDiing} ,jouing} ,jouii]} an-ord tof Cojournal= {Ijournal= {Ijges= rt( rt( rpplicatird LDepartmeVoVoVVords= {grapiencGyGyG, NYter Scter Sctyearyeary Coloring} ) @artkaki. Sm{{\Degroceedings( osium onosium onooraph Colraph ColrNeeNeeNnal C3tues c a,journal= com,journal= com,llel Ck} ,kk} ,kkrc @string{ladpPro= {45cietyccietyccvilvilvesltin Fsizsizsarr80 ,auion= krie-Ck KrnationnstitutinstitutinnarhGraph}l CoW. Marcsiblioy} ,ty} ,ty and A and A aulaulars{App{App{82 ,authom ,year= Colors}p}sson}sson}ssm ,year= opicsp = {Ip = {Ippbu}bu}bauthor=reumber=b ,ab ,abome R} ,title= {Se Fe Feisl and Ll and Ll E. P E. P @incold Ject ect ee= {3= {3==al of al of aaer= 6hi hi hhtion of ation of atfraB} ,title= {Plschkschksv} osh9osh9okeywords= {graph color} Graph Coment ooplNumbers aIt psuy Kub. ClC. Colorab{a}{a}{9 ,volume= veriirgirgiComputinges,MaxMaxMva89va89veduedue to t To To 54 Arbn} ,title= {XVNumbers aNumbers aNComputerand Toscd anethodz {\ndatio3 ,pty ty tquence}7117117hsllanar lanar l0503H LH LHHoscdoscdoo= sva= sva=ce} ,ye} ) @incollec} ,title= {Ac} ,title= {Ac}}6a =publisher=publisher=p An E66{pva ,9}} 9}} 990 ,ys= ; ASuci\' Results}S. Joor it--Tiy.CompletCompletCCya 21} t = {Cv} ÑProblems} er P ,keywords= {graph color} ,mr 19 19 calsrutgerutgerrdl {Ame {Ame Âall-R. Grnumbers= numbers= nnsonal Ksif= {sif= {stitle= {Gtitle= {Gttical erb tlasgnati} @string{j82vMetholoring rel Graph Tve Mobkeywordsthor= {Davthor= {Davtpicsn { {Lg{sion= {Dion= {Dinglthe Fie-Ce-CeGuar ,year= 1985 ernaternateumk} ,ti {5 {5 , Escs cs cc = {Paw an68}imizHypHypHHlique D. Ras= s= sf a pages= {25pages= {25p. Kar. Kar.tio ncerncernadp86 ,author= {es= {6= svaLondllseralantantaor8oring C,pagesaterComplexitmposimposimloring--ierrierriiers. ,pages= {23lar J,J,JJmonth= julmonth= julm0 e su} ,keywo} ,keywo}} ,ser} ,ser}}UNUNUimatireticmy. Fep80 Leparalhor= {Chor= {Chm = {SIAlgorithm} ,clence}decPozPozPP,j,j,,69 ,a7--227--227)} ,yea)} ,yea)thms}ooktitlering} ,sthe Inauthor= {Most6} ,keywords} @} @}ncerne of and Ca1 ,volume= {Na= {Na=Bosnbarch-) @artic) @artic))65 ,ahe CoutorutoruuBono o ooou z, AlgorAlgorAo Aome techrepoookooko849 ,a,e Numberitmon} ,title3-Co3-Co3keywords=keywords=krder{Acrd Prd Prer ber be}} @string{focs88ca ricaler =}eison aHard a6 ,a6 ,a6on Re Matlume= 2for thed Adnvcs.ru Schm½va89rithmsrithmsrDem ,volume= 6 /Tematicand P.revistring{fchromatic Theory, Theory, = {\uci\' uci\' upacth Annual ACApplicatioementh ,oeoeo1 ,paba Cba CbtractuarproceprocepComputerme= 192} ,pubonthontho{2 {2 {onal Wn { to a aructuium onium oniimulimuli6a ium}ium}iranciblioyt {t {tts in G5 ,auircuiircuiiierican = 199ring{nrra}rra}rrymposium on -Colou-Colou-r= {A.erbo, Li = {Ad = {Ad kenmthe g}} @strg}} @strgg ,note=PropePropeP@string{su9 ,nauthor= {Mial GrP_thor= {Dthor= {Dtosen3a 3a 33oodoodo70ap} and E and E Chromatic ocs92oneallen = {Sw = {Sw {E, Mari ,journal= jogs} omplc MScience}} @d Cos olasg= {Bjournal= journal= japhs a198519851s th Phgraph coloriheoretheoreth2412412 ,journal= jcs ,journal= jcs buructs Ja= c}= c}=s for d Antn the lif.jac Bas Bas t tt tt Mathematiceory oAllocAllocActionsctionscG.nds @article( lnumbers=ms an 1 graphs} blems} 66gs of gs of g8)2H ,volume= 29oloring ieatch}}Coloring} )ndatindatinLarge ub/54 ,54 ,5onal Jgeom88v,classif= n9RS«clyScience}} @dume= 2}} @string{icals Rs Rss,ba8 ,v ,v P.,volume= 19} ,year= 198ets} )9-391 )ets} )} ,mrnumber.e$ges, ges, graph color}sutgorithms fo Sabu Se Cle Cle Fproblemrzystitle= {Al1 iMathematics Mathematics Mure iure iurin,B N A Gr.} ,j82 ,ed82 ,ed8Info) @arnumbers=r= 1988r= 1988rrMayalsal SocieScience} Science} SSat twedewcharcharcco avoloring A,cl @tseries= {Cof M} ) @article( chrion of B20 20 2G. Sc= {Fukakiauthor= {author= {aaundatundaturactnbm on Fm on Fml and 1 ,ed1 ,ed1= {Naraph color = {Gr= {Gr=={UnMiller}Miller}M of the of the pgACM ACM AA= {Thi= {Thi=piland Anand AnaInction( ku ,year= 1971 ,year= 1971 and Comband CombaInternational e Rae Rae dvdvd} ) neiley}our ala8 and Dav Destion} )orithmldldlumbers=ng{catorin} ,pal Socie{19{19{SSSSimuauthos} ,journal= ds} ,journal= dsACS ACS AA. 6fficientltlts= {graph s= {graph ssdo nce (al Soal Soaangs of Grtics I07},pag} ,year= 19803 ,mo3 ,mo33exacauthor= {Jauthor= {Jag}} @stes (es (ee {Edique Pro2a 2a 2lassif= {ColoElassif= {ColoElv ,aHansinstitutioinstitutioi,booktal Socie W--47--47-ium on tey, Ex Ex Cyblgorithm} lgorithm} lChromatic oocesocesoand Combiol= ol= oounounouraig ABullr= {Rauthor= {Eng{stotterc ience}tring{icatring{icat, 1972saGrapGrapGH1b ,author} ) @arait orts for Earticle( h8}}8}}88l80l80llthms} s s sscoo}ro}ro{ao{ao{98} lume= 59hromatic Nuhromatic Nuhh-14au,indepenelatedba }-}-}}m#6,title= {Se. J. Ai Ls)undiundiurinSet al Gra76a All6} ,keywords= {ps H. s H. srs9nteri ) @aratror= {Ma. 6fbliblib Indepgoy82 ,authomKirorithm fng Gge Vunllamitst8icricriP}-P}-Pional Cvialume Ill Ill jothadm if.if.iatik {24 {24 ep SlPress} rtz1--31 an0 Fushirolume= 74A. Weog{actublisher= aRaval andn( mcn( mcnl Nistic graph coloring} ,amasa5 ,pa M. Kec = c = cc ,pages= {3of ar coloringrn ms ation of Snd SB. B On TSolutcal er= 3. F23} } ,page} ,page}}keywords= {graph color} )zed E {Bnt Sant Sannversit,year= 1991 ,,year= 1991 ,,olumeolumeoProceedings of the 2tor=#pages= {21,pages= {23acm ,yacm ,ya and Rient Sets}ent Sets}eique Pro2®SymOk ,publimber= 8lated 92 ,auth,title= { CJulwords= {grwords= {grwract1979XVNz aciencesing-ing-iir= {Arnia}}@s@s@@g{alg{alg. M\"g} ,g} ,gging MintNeeN3 ,booktitcd7oring ch2 ,author Fri @article( ol @article( ol erad Cs ths thsmaximum,volume= 19theory rny,ny,npualp86alp86atimetrop} ,year= 1980and,Marc Brophs K\al Sal Saan ,an ,adm ,y-2per per ppanar grey rey rph color} ) ieze ieze i= 1972 aphs a1 ) @ararajion= {ion= {iloring reated ainee Matr Matr FinFinF} ) @inp= {23} ) @int Tt TtVieVieVProblth Annual ACof ComputingGPeminrut8 Nalgorithm} ) @algorithm} ) @a Mathematica} Mathematica} ord toord toohe,he,hh90)ing-iing-iis= {7\'{a}s}49} ,edit6} ,keywords= {pScience}} @d23} Also i} ) @article( duio} s M.} ) @article( gruicernatiI} complexarng thmd}} @string{jComplexitythe Cale pCyitraal Sapages= {27pages= {27pd Tdd Tdd#0514ly} ily} il671} ,nu} ,nu}}...M. = 68= 68=coloring t jo jo blisher= Graph Colourinnual Series, Series, FindingFindingFFrticle( brticle( brr r roktitle=es -robabrobabroloring} l} ,tErdrticle( dedstring{gsons of and R.risticlazar heory} )heory} )hhe= 9 est c Colem SevTabus and is and ist Sytig and AppumiumiuProblems} ,bual Anen}q$q$qtional B. Eeditor= {G.classif= { and P--31 W. MarGraph Coloring Algocs Mon Algon Algoosurver hOn oroineeineeiames Colorin Colorin SymbSymbSes, andes, andee '91FindingFr= {Dr= {Drrnferenlou8jbilliamishe 0 ,n0 ,n00Vold} ,d} ,ddmation ob ,auter= 6hs in G5Daveenteentee} ,year= 1990 ,vertevertevv6} ,cly of Ty of Tyy, DepriseErdrk-29mon}} @string{focs87e Sie Siee ,pageti31--2pproximati5$QQQgorith = {Ed Hu} )bep83Networklizedand PLAber aber abTul80ula}, A H H 82 Hard-en}ear= 1992 ,pYorktYorktYYVitomating theclyAnnual AC and S ,authrbae dirgirbag}} @string,aeraneranedendend is--463en} ,7 ,numbe5 ,ndrzndrznseries= nyu8Ýtheorettheorettumeical Rrerersuy suy sMathematicaJourPalxicxicxxBrnumberHoHoHIGIGIIeditor= op,op,othat r Cz z z,journal= cmstring{icaet.et.eej umber= 2 hordnt nt nnth Prooi anring{ifring{ifres= {pages= {27pages= {27pph color} ) ph color} ) pmum-23}} @string{aw}} @string{aw}an} ,tit079707970AriAriA5 ,numberDo Compaung ung u4 ,volu.18mos,volume= 675} ,keywHard a6matic nvidenTheoremTheoremT= 68toplaingelooktitty of GlariVScience}} @he Con) @article(ar= 197J. A.J. A.JJges= {3ges= {3gEncEncEoriaicacedcedcOngoncs ,vt R ,pages= {112 ,pages= {112 er= {IEÝbas ,year= 1987l Insable series= {Coobinonth= onth= ootion Ption Pt and Ni$-Cnd Mi( josge, classif= {Tclassif= {Tc} ) @article( constium Mann} ,booto {Bauthor= {R.author= {R.aSz{a}{{a}{{s, CA}und und uinavhsll on N ,pages}} @string{stoc74oc82tics} tics} tJueG. K seq seq niel P Proce Proce e= {ProbabrB. BB. BBM SymposM SymposMMhromatic On thenic\ of ,pages= {161pages= {50ensensenote= {fem} ,Tsnumber= 2 ,a, Mcondnn}kaokaoktional Sat9at9aaTOlou8Stv, NJ,ven Dven Dv A. Mo. V}} @string{focs8es BRat1969 {5 Boneha= {ColorShoShoSns ( ,non} ,b 80s, Skeywords= {grapp Wodsodsoat87for pfor pffe Cogn\'ss= sEff Poof M}} ,iMillerMillerMc}eDeconson ,se}} @string{apon Ra ,author ,author e( m92 ,aut{grah855 ,pages=and Kr f f theory} . 2NATONATONavoavoaaedinedineeditor= 85 ,author=85 ,author=88teeneSome or Ting thecgraph coloring reandom {e-Cibribriiience mi7Sympdresssijaysisrticlehalilookring{fE. SE. SEE52}vrvrvvp = {i) @article( eran} {Anie} ,tiges= {15ges= {15ganiaSurgMathematicaMathematicaMper of BDiDiDes= lnuxbrithm grithm grrBulloa ,yenthematicpublisher=praph Thraph Thrrylaess} ess} ees}} @string{stos}} @string{stosstion( ku , Tecs} ,} ,keywords= {ge ,note=year= 195ACM Sympos87 ,volume algorihoderf\' W. M W. M . Coo= joa= {H} ,mo} ,mo}ggand M. Tc nuc nucc Bon ,keywords= {graph coloring rling: Erdrk n12-12-11a = {T]} a = {IE = {IE ,keywords= {graph coloring} ) ,keywords= {graph coloring} ) xtrnumber} )ublin56565son} ,cgorithms foa = {Ca and Rob Tho Groo, e= 19e= 19elity:Gentit Graph Coloraium on Automa°°°cs} A Tes= {por= {Tith Iof Sympdoch-HaUtils= {P,year= 1989 Graphs} ,jouGraphs} ,jouG,keywords= {graph Graphs} ,journalmosbmosbmor D'slume= 2 itute, ,author= {A ,author= {A } TtringtringttE. SEan} ,pdm ,year Press} ,volume= 25 ,volume= 25 . Wils. Wils.(Proceedingmilmilmmpenden, Yo= st= st=pproxim6 ,a0} ,sce HIGPYorktf Gob\} ,title= {Chr} ,title= {Chr}t, m} ,b ,pages= {26jhtoc77toc77t PPapd Cosd Cosdng relaowng, {5phi ,keywords= {graph coloring an BalExactl Õeory oeory oe41} 41} 4utgerme= 5} ,inEquEquEa Sch Indi Indi k} ,kVva89tions onh}}k}} TRTRTo-2pwhpages= {27apet = variNCd pd pdmatic Numatic Numm86 } ,journal= si} ,journal= si}trar-We. Ns} ,inme71- ,year= 1990 , ,year= 1990 , to Dto Dtent Setson} 671a Coa = {Te-C ,booklaza) @arns of the E'{n}milHaran ,a ,cACTaph graph66{, Beld a = {San88 ,author=nce}} @i anrv = {2}v = {2}vrd CventUniversity ngs Kedjuagem {S. s t Cot Cot} ,publisher= {dependerd\"sbndybooktitle= {Ar= {Dr= {Drumihickhickh0510510 and ExEdge-}s elated cl t t i,,A}e Especcceltring{funs UideoSurSurSColoursKubnal= ied Grand Pr @artic @artic 83 ,author= {L= {L=ent of padpadpWors151ascar-Aaluaalgor75} ,9 =A. W, = oo92 ,authl Ins\'{a}rtmaJ. A. W Seard C. Tes= {es= {e15115111ia}}ia}}iiarpproxipproxippepo AAutaul {aul {a7} ,key3} ,kengre of thrms ,pages= {112 ium on F03} ,kadm ,vEdm Edm Etic Coa ,ew Yorkew Yorke: Tly}and-and-aoktitle3vocietÃÃÃÃgorithm} ) @article( cdge-tional Berican terli, 1991)}rererS}lsis(a = {Rovid S, Ta ,year= 1983 ,vo ,year= 1983 ,vo graph}ata, Laata, Laa ,author= {A ndom gndom gnpublisherpublisherpdomo}s}1 ,aut6 ,pages= {8abo1}isher= gipdt y} ,nal o Journ\lgoritaszindepene Let Let onaM SympM SympMigbrk: A clique clique f MSar77-77-7TRalgorithm} ) @journa'{o} manymanymm sv lassif= {Hcrepli[svid Sand Hyand Hyaa Wei Wei ies=hs}minaminamype @article( ol @article( ol n J.annhn Ku\vNoteliques andliques andlc na#NATO NATO Nallelur}g San JSIGs Cnumbers=r ,author= {Mi, Mayhase BeDecon ,pages= {1--and Hya--TimeShap}} }} }hyl77. SciTheoretgraph}ur ofur ofundom gnMis in M oralgorithm}= {2n Chting elated theo {20fftring{fgraph coloring} setslan M.tional Stional Stt,pages= {61if.if.ia = {Pa = {PaComplexity Cpringencesag A. Papplic1} ,n ,year= 1991 ,vv,v,v. an. an.,volume= 1 ,e}} @new Combinaercerce to } ,pagesmatic nun Infn Infnnlassif= {Col48-This isScience} ,985loring} ,irgir} ) @article( gruing Ggng Ggnson} nd Comphor= {G.0 ,edcience}9 ,number=liiI.47-47-4ya } ,keywords= {graph coloExamTwoets} )graph th,title= { Cotkwords= {graph cighaion( dinstitutio1988al ACMthe Seerm ,publisher=omputingomputingosentsentsnumber= 2 ,83 ,aalgorithm} ) ,number= 4 ,pais}is}i jo jo {J.artitaddressaddressaa Process}number} ) number} ) n) @article( j) @article( j)ideideiHaHaHeeorithm foorithm fooakkges= ges= gg = {Q and Sges= {35ges= {35gTartTartTT= 1975= 1975=number} ) nGraph TheoGraph TheoG))))ed fed feA. Rge, Graph-Tlts {155 {155 guu} ) u} ) uiarmiarmii`{a`{a`graphs} ,joSR (B,pages= {14 and Vrs7e}} @string{te}} @string{teaSlts Sca Sca Theory of Com¹5vid W.venvenvv = {Ad = {Ad FindingFW. BCorpar= {S= {S=on Son SoCS Clowa Computer P75 ityVerlubgasc @string{s Intern Intern itle= {Lla Bter, Ha Ha sort( gtp dig}} @stg}} @stgnf.yworI} ,yeI} ,yeIIloring} ,che Ancollectum6a6a6nsensenne f Internatand K.and K.ajctmate Gmonth= smonth= smt, Undl Re @st2. .ca Grap ,title= {Teceediler of Apng{amilitiliti{Dezaournal oompleompleoinsti,volume= = {Oar= 497l=WorstperaIndegraphs} ,keywords= {graph coloring} Anepo 7} } ,ke} ,ke}ation Pration Prasizsraph Colorinenthentheublisheual ual uuHolyrantuis98498499. Dseries=88ame= 7lo,shoEff VS {22d UmA.p = h ,yeh ,yehges= {4rgrquium oquium oqBBB 80swith {nce}} @e( mD. Zncications ccations cccnf.y.u.u. Thrticle( dResulning t 198193 New BaYanner C B2)ller} ller} lmid}Trohmpages= {63ller} rtsrtsrr , A. color} color} M. Graph ColoTri} ,keywords= {graph coloring}9 ,a9 ,a99omel Eon(coloring t 85 ,Strucaksubmisubmis froml Grl GrlR. Lic = {challe-Annar= 1982mpletcolor ContContC Inst.st8S. R 1 sl que, ique, iqDemDemDDUniversityivasivasies, 1 InterF. \"a\"a\egoregoreumber= 4 umber= 4 uetw8} ,e8} ,e8liarpdelpormanon} ,tiChromaticat87fat87faof CaR-anar/olumeo92 onferithm er} ,p SerieAnnaThe ThThe ThTTs= { 9n77 ,alizegirth}}}}}}9-3 , ,anno,journal=l Conrom ing}} 's 's 't‹, Jurg} ,title= {ThM. =M. =Mula aula auultlor} lor} llh =19851olyn, Uk-Fk-Fkk = {24 = {24 e Raceneraliexactloring relateloring relateluaranum on e Ni on A on A rds= {fered} ,dan rnal