@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{longman = {Longman Scientific \& Technical}} @string{longmana = {Longman house, Burnt Mill, Harlow, Essex, UK}} @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{pitman = {Pitman Research Notes in Mathematics Series}} @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( acmo99 ,author= {Dimitris Achlioptas and Michael Molloy} ,title= {Almost all graphs with 2.522$n$ edges are not 3-colorable} ,journal= {The Electronic Journal of Combinatorics} ,year= 1999 ,volume= 6 ,pages= {\#R29} ,note= {http://www.combinatorics.org/} ,keywords= {threshold bounds} ) @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} ) @inproceedings( alka94 ,author= {Noga Alon and Nabil Kahale} ,title= {A spectral technique for coloring random 3-colorable graphs (Preliminary Version)} ,booktitle= {Proceedings of the twenty-sixth annual {ACM} symposium on the theory of computing} ,year= 1994 ,pages= {346--355} ,keywords= {easy-hard} ,annote= {Show a polynomial time algorithm that with high probability finds a 3 coloring of a 3-colorable graph if $p \ge c/n$ for $c$ is a sufficiently large constant. The algorithm is based on spectral techniques. Note that for $c$ small enough the graph almost surely has maximum degree less than 3, and os is easily colorable. This leads to question, is there an algorithm that works for all $p$? } ) @article( alka97 ,author= {Noga Alon and Nabil Kahale} ,title= {A Spectral Technique for Coloring Random 3-Colorable Graphs} ,journal= {SIAM Journal on Computing} ,year= 1997 ,volume= 26 ,number= 6 ,pages= {1733--1748} ) @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( alo97 ,author= {Noga Alon} ,title= {A Note on Graph Colorings and Graph Polynomials} ,journal= jctsb ,year= 1997 ,volume= 70 ,number= 1 ,pages= {197--201} ,keywords= {graph coloring polynomials} ) @article( anbi93 ,author= {M. Anthony and N. Biggs} ,title= {The mean chromatic number of paths and cycles} ,journal= dm ,year= 1993 ,volume= 120 ,pages= {227--231} ,keywords= {greedy asymptotic chromatic number paths cycles} ) @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 of 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( bccp93 ,author= {EGON BALAS and SABASTIAN CERIA and GERARD CORNUEJOLS AND GABOR PATAKI } ,title= {Polyhedral methods for the maximum clique problem} ,booktitle= {Cliques, Coloring, and Satisfiability} ,publisher= {The American Mathematical Society} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,pages= {11--28} ) @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} ) @inproceedings( beep95 ,author= {Richard Beigel and David Eppstein} ,title= {3-Coloring in time $O(1.3446^{\textstyle n})$: a no-MIS algorithm} ,booktitle= {36th IEEE Symposium on Foundations of Computer Science} ,year= 1995 ,pages= {444-452} ,url= {http://www.eccc.uni-trier.de/eccc-local/Lists/TR-1995.html} ,keywords= {Worst case bound, theory, exact algorithm} ,annote= {An algorithm based on a common generalization of 3-coloring, 3-SAT 3-edge-coloring and 3-list 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} ) @Incollection{BFZ90, author = "Bertrand Braschi and Afonso Galvao Ferreira and Janez Zerovnik", title = "On the Asymptotic Behaviour of Parallel Simulated Annealing", booktitle = "Parallel Computing 89", editor = "D.J.Evans and G.R.Joubert and E.J.Peters", publisher = "Elsevier Science Publishers B.V. (North Holland)", address = "Amsterdam", year = "1990", pages = "263-268", note = "ISBN 0-444-88386-X" } @inproceedings( bgs95 ,author= {Mihir Bellare and Oded Goldreich and Madhu Sudan} ,title= {Free Bits, {PCP}s and Non-Approximability---Towards Tight Results} ,booktitle= {36th Annual Symposium on Foundations of Computer Science} ,year= 1995 ,pages= {422--431} ,organization= {IEEE} ,address= {Milwaukee, Wisconsin} ,keywords= {free bits non-approximability tight results} ) @incollection( big90 ,author= {Norman Biggs} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {Some Heuristics for Graph Colouring} ,pages= {87--96} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {greedy algorithm} ,classif= {Vertex Algorithms Survey} ,annote= { A brief survey of simple heuristics with some theory applied.} ) @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} ) @article( blu94 ,author= {Avrim Blum} ,title= {New approximation algorithms for graph coloring} ,journal= jacm ,year= 1994 ,volume= 41 ,number= 3 ,pages= {470--516} ,month= may ,note= {an O(n to 3/8 polylog(n)) algorithm} ) @article( bmn92 ,author= {Amotz Bar-Noy and Rajeev Motwani and Joseph Naor} ,title= {The greedy algorithm is optimal for on-line edge coloring} ,journal= {Information Processing Letters} ,year= 1992 ,volume= 44 ,number= 5 ,pages= {251--253} ,keywords= {greedy on-line} ) @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} ) @book( bomu78 ,author= {J.A. Bondy and U.S.R. Murty} ,title= {Graph Theory with Applications} ,publisher= {The MacMillan Press Ltd} ,year= 1978 ) @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( bost88 ,author= {I. Bouwer and Z. Star} ,title= {A question of protocol} ,journal= {The American Mathematical Monthly} ,year= 1988 ,volume= 95 ,pages= {118--121} ,month= {February} ,keywords= {protocol greedy coloring} ) @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} ) @inproceedings( brcu95 ,author= {Mark Brockington and Joseph C. Culberson} ,title= {Camouflaging Independent Sets in Quasi-Random Graphs} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge} ,year= 1996 ,pages= {75--88} ,editor= {David S. Johnson and Michael A. Trick} ,publisher= {American Mathematical Society} ,note= {preprint available http://web.cs.ualberta.ca/\verb+~+joe/} ,series= dimacs ,volume= 26 ,keywords= {antigraph for clique algorithms} ,annote= {In this paper, we look at the problem of how one might try to hide a large independent set in a graph in which all other independent sets are significantly smaller. We present an improved random graph generation system, DELTA, which increases the range of maximum independent sets that can be hidden from these techniques.} ) @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} ) @Techreport{BSZ98a, author = "Pete Burge and John Shawe-Taylor and Janez Zerovnik", title = "Graph Coloring by Maximal Evidence Edge Adding", institution = "Preprint series Dept. Math. University of Ljubljana", year = "1998", volume = "36", number = "613" } @Techreport{BSZ98b, author = "John Shawe-Taylor and Janez Zerovnik", title = "Adapting temperature for some randomized local search algorithms", institution = "Preprint series Dept. Math. University of Ljubljana", year = "1998", volume = "36", number = "614" } @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( cade01 ,author= {Massimiliano Caramia and Paolo Dell'{O}lmo} ,title= {A lower bound on the chromatic number of {M}ycielski graphs} ,journal= siamdm ,year= 2001 ,volume= 235 ,pages= {79--86} ) @article( cade02 ,author= {Massimiliano Caramia and Paolo Dell'{O}lmo} ,title= {Constraint Propagation in Graph Coloring} ,journal= {Journal of Heuristics} ,year= 2002 ,volume= 8 ,number= 8 ,pages= {83--108} ) @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} ) @techreport( capa93 ,author= {Bob Carter and Kihong Park} ,title= {How good are genetic algorithms at finding large cliques: an experimental study.} ,institution= {Boston University} ,year= 1993 ,type= techrep ,number= {BU-CS-93-015} ,address= {Computer Science Department, Boston, MA. 02215} ,month= oct ,annote= {Results show that pure GAs on the clique problem are not too efficient, and need heavy customization. Also looks at parallel versions. Expect GAs to be perhaps competetive with simulated annealing.} ) @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} ) @inproceedings( cbp95 ,author= {Joseph Culberson and Adam Beacham and Denis Papp} ,title= {Hiding our colors} ,booktitle= {CP'95 Workshop on Studying and Solving Really Hard Problems} ,year= 1995 ,pages= {31--42} ,address= {Cassis, France} ,month= sep ,abstract= {In this paper we describe several classes of $k$-colorable graphs which have various defining parameters. These are often motivated by questions of how to hide colorings that are significantly different than the colorings likely to be found by various heuristic algorithms.} ) @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} ) @article( chd95 ,author= {Daniel Costa and Alain Hertz and Olivier Dubuis} ,title= {Embedding a Sequential Procdure Within an Evolutionary Algorithm for Coloring Problems} ,journal= {Journal of Heuristics} ,year= 1995 ,volume= 1 ,pages= {105--128} ,keywords= {genetic algorithms} ) @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} ) @incollection( che90 ,author= {Amanda Chetwynd} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {Total Colourings of Graphs} ,pages= {65--77} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {total chromatic number theory} ,classif= {Survey Graph Theory } ,annote= {A survey of total coloring graph theory problems.} ) @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} ,annote= { various sequential algorithms tested including a variation on Brelaz DSATUR in which the color of least impact (greatest prohibition) is used, with revised colorings based allowed} ) @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( cohe96 ,author= {Daniel Costa and Alain hertz} ,title= {Ants can colour graphs} ,journal= {Journal of the Operational Research Society} ,year= 1997 ,volume= 48 ,pages= {295--305} ,keywords= {Ant system, Graph coloring, Evolutionary search, Ant algorithm, Assignment type problem, Collective performance, Evolutionary method, Graph colouring} ) @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} ) @article( cos93 ,author= {Daniel Costa} ,title= {On the use of some known methods fo $T$-colorings of graphs} ,journal= aor ,year= 1993 ,volume= 41 ,pages= {343--358} ,keywords= {generalized coloring, tabu, simulated annealing,frequency assignment, branch and bound, heuristic procedure} ) @article( cosz90 ,author= {K. Corr\'{a}di and S. Szab\'{o}} ,title= {A Combinatorial Approach For {K}eller's Conjecture} ,journal= {Periodica Mathematica Hungarica} ,year= 1990 ,volume= 21 ,number= 2 ,pages= {95--100} ,annote= {Related to a hard independent set problem} ) @article( coth82 ,author= {E. J. Cockayne and A. G. Thomason} ,title= {Ordered Colourings of Graphs} ,journal= jctsb ,year= 1982 ,volume= 32 ,pages= {286--292} ,keywords= {sequential ordered coloring theory} ) @article( cuge01 ,author= {Joseph Culberson and Ian Gent} ,title= {Frozen Development in Graph Coloring} ,journal= tcs ,year= 2001 ,volume= 265 ,pages= {227--264} ) @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} ) @misc( culgrcl ,author= {Joseph Culberson} ,key= {culgrcl} ,title= {Graph Coloring Resources} ,howpublished= {on-line} ,note= {http:/www.cs.ualberta.ca~joe/Coloring/index.html} ,abstract= {A collection of programs, bibliogrpahy and links on graph coloring.} ) @inproceedings( culu95 ,author= {Joseph C. Culberson and Feng Luo} ,title= {Exploring the $k$--colorable Landscape with Iterated Greedy} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993} ,year= 1996 ,pages= {245--284} ,editor= {David S. Johnson and Michael A. Trick} ,publisher= {American Mathematical Society} ,note= {preprint available http://web.cs.ualberta.ca/\verb+~+joe/} ,series= dimacs ,volume= 26 ,keywords= {iterated heuristic vertex coloring algorithm } ,annote= {Explores the $k$-coloring landscape under iterated greedy, TABU, and MAXIS. A variety of graph classes are used, including flat graphs.} ) @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} ) @article( dgp94 ,author= {Marc Demange and Pascal Grisoni and Vangelis Th. Paschos} ,title= {Approximation results for the minimum graph coloriing problem} ,journal= ipl ,year= 1994 ,volume= 50 ,pages= {19--23} ,keywords= {polynomial approximation, unwarranted solution approximation} ) @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} ) @article( diwi83 ,author= {John D. Dixon and Herbert S. Wilf} ,title= {The Random Selection of Unlabeled Graphs} ,journal= joa ,year= 1983 ,volume= 4 ,pages= {205--213} ,annote= {A method for generating random unlabeled graphs, given the computation of $g_n$.} ) @article( doha98a ,author= {R. Dorne and J.K. Hao} ,title= {A new genetic local search algorithm for graph coloring} ,journal= {Lecture Notes in Computer Science } ,year= 1998 ,volume= 1498 ,pages= {745--754} ,note= {www.info.univ-angers.fr/pub/hao} ) @inbook( doha98b ,author= {R. Dorne and J.K. Hao} ,editor= {Voss, S. Martello, I.H. Osman and C. Roucairol} ,title= {Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization} ,chapter= {Chapter 6: Tabu search for graph coloring, T-colorings and set T-colorings} ,pages= {77--92} ,publisher= {Kluwer Academic} ,year= 1998 ,note= {www.info.univ-angers.fr/pub/hao} ) @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} ) @inproceedings( epps01 ,author= {D. Eppstein} ,title= {Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction} ,booktitle= {12th ACM-SIAM Symposium on Discrete Algorithms} ,year= 2001 ,pages= {462--470} ,note= {ACM Computing Research Repository, cs.DS/0011009} ) @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} ) @article( ewhk98 ,author= {Thomas Emden-{W}einert and Stefan Hougardy and Bernd Kreuter} ,title= {Uniquely Colourable Gaphs and the Hardness of Colouring Graphs of Large Girth} ,journal= {Combinatorics, Probability and Computing} ,year= 1998 ,volume= 7 ,pages= {375--386} ) @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 ,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} ) @inproceedings( flfe93 ,author= {Charles Fleurent and Jacques A. Ferland} ,title= {Object-Oriented Implementation of Heuristic Search Methods for Graph Coloring, Maximum Clique, and Satisfiability.} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,pages= {619--652} ,series= dimacs ,volume= 26 ,annote= {A generral framework for mixing TABU and Genetic algorithms for coloring, maximum clique and satisfiability.} ) @article( flfe95b ,author= { Charles Fleurent and Jacques A. Ferland} ,title= { Genetic and Hybrid Algorithms for Graph Coloring} ,journal= aor ,year= 1995 ,pages= {to appear} ,annote= { By creating a hybrid of TABU and genetic algorithms, the authors obtain quality solutions fo some graphs.} ) @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{ frmc97 ,author = {Alan M. Frieze and Colin McDiarmid} ,title = {Algorithmic theory of random graphs} ,journal = {Random Structures and Algorithms} ,volume = {10} ,number = {1--2} ,pages = {5--42} ,year = 1997 } @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( fsm93 ,author= {Martin F\"urer and C.R. Subramanian and C.E. Veni Madhavan} ,title= {Coloring Random Graphs in Polynomial Expected Time} ,booktitle= {Proceedings of the Fourth Annual International Symposium on Algorithms and Computation, ISAAC'93} ,year= 1993 ,pages= {to appear} ,publisher= {Springer LNCS} ,month= dec ) @inproceedings( fur95 ,author= {Martin F{\"u}urer} ,title= {Improved Hardness Results for Approximating the Chromatic Number} ,booktitle= {36th Annual Symposium on Foundations of Computer Science} ,year= 1995 ,pages= {414--421} ,organization= {IEEE} ,address= {Milwaukee, Wisconsin} ,keywords= {approximate chromatic hardness} ) @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{FZ93, author = "Afonso Galvao Ferreira and Janez Zerovnik", title = "Bounding the probability of success of stochastic methods for global optimization", journal = "Journal of computers \& mathematics with applications", volume = "25", pages = "1--8", year = "1993" } @article( gaha99 ,author= {Phillippe Galinier and Jin-Kao Hao} ,title= {Hybrid evolutionary algorithms for graph coloring} ,journal= {Journal of Combinatorial Optimization} ,year= 1999 ,volume= 3 ,number= 4 ,pages= {379--397} ,note= {www.info.univ-angers.fr/pub/hao} ) @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( ges91 ,author= {Ira M. Gessel} ,title= {A coloring problem} ,journal= {The American Mathematical Monthly} ,year= 1991 ,volume= 98 ,pages= {530--533} ,keywords= {greedy algorithm coloring problem} ) @article(gewa94, author = "Gent, I.P. and Walsh, T.", title = "Easy Problems are Sometimes Hard", journal = AI, vol = 70, pages = "335-345", year = 1994) @article{gewa96, author = "I.P. Gent and T. Walsh", title = "The Satisfiability Constraint Gap", journal = AI, year = 1996, volume = 81, pages = "59--80"} @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( 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( 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( 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( glo90 ,author= {Fred Glover} ,title= {{TABU} Search --- Part {II}} ,journal= {ORSA Journal on Computing} ,year= 1990 ,volume= 2 ,number= 1 ,pages= {4--32} ) @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( gosp93 ,author= {Mark Goldberg and Thomas Spencer} ,title= {An efficient parallel algorithm that finds independent sets of guaranteed size} ,journal= siamdm ,year= 1993 ,volume= 6 ,number= 3 ,pages= {443-459} ,keywords= {parallel independent sets} ) @inproceedings( gpr93 ,author= {Fred Glover and Mark Parker and Jennifer Ryan} ,title= {Coloring by tabu branch and bound} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,pages= {285--307} ,publisher= {American Mathematical Society} ,series= dimacs ,volume= 26 ) @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} ) @article( hal97 ,author= {Magn{\'u}s M. Halld{\'o}rsson} ,title= {Parallel and on-line graph coloring} ,journal= joa ,year= 1997 ,volume= 23 ,number= 2 ,pages= {265--280} ,keywords= {parallel on-line on line} ) @article( hala94 ,author= {Refael Hassin and Shlomo Lahav} ,title= {Maximizing the number of unused colors in the vertex coloring problem} ,journal= {Information Processing Letters} ,year= 1994 ,volume= 52 ,number= 2 ,pages= {87--90} ,keywords= {maximizing unused colors} ) @article( hama97 ,author= {Hac{\`e}ne A{\"\i}t Haddad{\`e}ne and Fr{\'e}d{\'e}ric Maffray} ,title= {Coloring perfect degenerate graphs} ,journal= dm ,year= 1997 ,volume= 163 ,number= {1-3} ,pages= {211--215} ,keywords= {perfect degenerate} ) @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( hdg98 ,author= {J.K. Hao, R. Dorne and P. Galinier} ,title= {Tabu search for frequency assignment in mobile radio networks} ,journal= {Journal of Heuristics} ,year= 1998 ,volume= 4 ,number= 1 ,pages= {47--62} ,note= {www.info.univ-angers.fr/pub/hao} ) @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} ) @article( hhk93 ,author= {Pierre Hansen and Alain Hertz and Julio Kuplinsky} ,title= {Bounded vertex colorings of graphs} ,journal= dm ,year= 1993 ,volume= 111 ,number= {1-3} ,pages= {305--312} ,note= {Graph theory and combinatorics (Marseille-Luminy, 1990)} ,keywords= {bounded vertex coloring} ) @incollection( hijo90 ,author= { Anthony Hilton and Peter Johnson} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {A Variation of Ryser's Theorem and a Necessary Condition for the List-colouring Problem} ,pages= {135--143} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {theory latin squares } ,classif= {Theory related} ) @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} ) @incollection( hofe90 ,author= {Fred Holroyd and Feodor Loupekine} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {The Four Colour problem is not dead} ,pages= {37--44} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ) @misc( hog94 ,author= {Tad Hogg} ,title= {Phase transitions in constraint satisfaction search.} ,howpublished= {A World Wide Web page} ,year= 1994 ,note= {\newline URL ftp://parcftp.xerox.com/pub/dynamics/constraints.html} ,keywords= {related topic} ,annote= {A collection of papers and links to the phase transition phenomena of constraint satisfaction search. Note the graph coloring is a special case.} ) @article( hogg96 ,author= {Tadd Hogg} ,title= {Refining the phase transition in combinatorial search} ,journal= ai ,year= 1996 ,volume= 81 ,number= {1--2} ,pages= {127--154} ,annote= {Tests transition on clustered grapsh using bst ultrametric, connected graphs and padded graphs where in every vertex has at least min degree. Also uses hidden solution problems. Tries to refine p.t. by counting triangles. } ) @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} ) @article( howi94 ,author= {Tad Hogg and Colin P. Williams} ,title= {The Hardest Constraint Problems: A Double Phase Transition} ,journal= ai ,year= 1994 ,volume= 69 ,pages= {359--377} ,annote= {exceptionally hard coloring problems} ) @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} ) @article( hrt86 ,author= {Denis Hanson and Gordon C. Robinson and Bjarne Toft} ,title= {Remarks on the graph colour theorem of {H}aj\'{o}s} ,journal= connum ,year= 1986 ,volume= 55 ,pages= {69--76} ,keywords= {hajos non-3-colorable calculus} ) @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} ) @article( huar85 ,author= {Lawrence Hubert and Phipps Arabie} ,title= {Comparing Partitions} ,journal= {Journal of Classification} ,year= 1985 ,volume= 2 ,pages= {193--218} ,keywords= {proximity matrices, measures } ,annote= {Measures useful for comparing partitions such as colorings} ) @article( hugo81 ,author= {Lawrence J. Hubert and Reginald G. Golledge} ,title= {A heuristic method for the comparison of related structures} ,journal= {Journal of Mathematical Psychology} ,year= 1981 ,volume= 23 ,pages= {214--226} ,keywords= {proximity measures for structures} ,annote= {This may be useful for comparing colorings} ) @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} ) @article( iwpi95 ,author= {Kazuo Iwama and Toniann Pitassi} ,title= {Exponential lower bounds for the tree-like Haj\'{o}s calculus} ,journal= ipl ,year= 1995 ,volume= 54 ,pages= {289--294} ,keywords= {hajos non-3-color construction} ) @incollection( jae90 ,author= { Fran\c{c}ois Jaeger} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {Graph Colourings and Link Invariants} ,pages= {97--114} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {related knot theory } ,classif= {Theory Kauffman polynomial} ) @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( jams89 ,author= {David S. Johnson and Cecilia R. Aragon and Lyle A. McGeoch and Catherine Schevon} ,title= {Optimization by Simulated Annealing: An Experimental Evaluation; Part {I}, Graph Partitioning} ,journal= {Operations Research} ,year= 1989 ,volume= 37 ,number= 6 ,pages= {865--892} ,month= {November-December} ,keywords= {related algorithms} ) @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} ) @book( jeto95 ,author= {Tommy R. Jensen and Bjarne Toft} ,title= {Graph Coloring Problems} ,publisher= wiley ,year= 1995 ,series= {Wiley-Interscience Series in Discrete Mathematics and Optimization} ,keywords= {graph theory} ,annote= {This is a collection of surveys of over 200 problems of various areas of theoretical graph coloring. It has a short survey on algorithms, mostly related to negative complexity results.It has many surveys of generalizations and special cases and is highly recommended for a theoretic background survey.} ) @inproceedings ( jocl98 ,author= { David E. Joslin and David P. Clements } ,title= { Squeaky Wheel Optimization } ,booktitle= { Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), Madison, WI } ,year= 1998 ,pages= { 340--346 } ,keywords= {graph coloring} ,url= {ftp://ftp.cirl.uoregon.edu/pub/users/clements/squeakyWheelAAAI98.ps.gz} ) @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} ) @proceedings( jotr96 ,title= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,publisher= {American Mathematical Society} ,note= {contains many articles on cliques and coloring} ,series= dimacs ,volume= 26 ) @article( jpy88 ,author= {David S. Johnson and Christos H. Papadimitriou and Mihalis Yannakakis} ,title= {How easy is local search?} ,journal= jcss ,year= 1988 ,volume= 17 ,pages= {79--100} ) @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} ) @article( kie88 ,author= {H.A. Kierstead} ,title= {The linearity of first-fit coloring of interval graphs} ,journal= siamdm ,year= 1988 ,volume= 1 ,number= 4 ,pages= {526--530} ,month= {November} ,keywords= {dynamic storage first fit interval graphs} ) @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 ) @inproceedings( kms94 ,author= {David Karger and Rajeev Motwani and Madhu Sudan} ,title= {Approximate graph coloring by semidefinite programming} ,booktitle= {35th Annual Symposium on Foundations of Computer Science} ,year= 1994 ,pages= {2--13} ,organization= {IEEE} ,source= {http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} ) @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} ) @article( krde82 ,author= {J. Krarup and D. de Werra} ,title= {Chromatic optimization: limitations, objectives, uses, references} ,journal= {European Journal of Operational Research} ,year= 1982 ,volume= 11 ,pages= {1--19} ,keywords= {chromatic optimization scheduling problems algorithms} ) @article( kri02 ,author= {Michael Krivelevich} ,title= {parse Graphs Usually Have Exponentially Many Optimal Colorings } ,journal= {The Electronic journal of Combinatorics} ,year= 2002 ,volume= 9 ,number= 1 ,pages= {R27} ,url= {http://www.combinatorics.org/} ) @article( kri89 ,author= {Igor K\u{r}\'{i}\u{z}} ,title= {A Hypergraph-Free Construction of Highly Chromatic Graphs without Short Cycles} ,journal= comb ,year= 1989 ,volume= 9 ,number= 2 ,pages= {227--229} ,keywords= { girth} ,annote= {A non-primitive recursive construction using a basis of bushes} ) @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{KZ96, author = "Sandi Klav\v{z}ar and Janez Zerovnik", title = "Algebraic approach to fasciagraphs and rotagraphs", journal = "Discrete Applied Mathematics", volume = "68", pages = "93-100", year = "1996" } @article( lash92 ,author= {Jeffrey C. Lagarias and Peter W. Shor} ,title= {{K}eller's Cube-Tiling Conjecture is False in High Dimensions} ,journal= bams ,year= 1992 ,volume= 27 ,number= 2 ,pages= {279--283} ,annote= {Related to a hard independent set problem} ) @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} ) @inproceedings( leco93 ,author= {Gary Lewandowski and Anne Condon} ,title= {Experiments with parallel graph coloring heuristics and applications of graph coloring} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,pages= {309--334} ,publisher= {American Mathematical Society} ,series= dimacs ,volume= 26 ) @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= {286--293} ,keywords= {graph coloring} ) @article( luya94 ,author= {Carsten Lund and Mihalis Yannakakis} ,title= {On the Hardness of Approximating Minimization Problems} ,journal= jacm ,year= 1994 ,volume= 41 ,number= 5 ,pages= {960--981} ,month= {September} ,keywords= {hardness approximating minimization} ) @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( masa94 ,author= {Carlo Mannino and Antonio Sassano} ,title= {An Exact Algorithm for the Maximum Stable Set Problem} ,journal= {Journal of Computational Optimization and Applications} ,year= 1994 ,volume= 3 ,pages= {243--258} ,note= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @inproceedings( masa95 ,author= {Carlo Mannino and Antonio Sassano} ,title= {Edge projection and the maximum stable set problem.} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge} ,year= 1995 ,editor= {David S. Johnson and Michael A. Trick} ,publisher= {American Mathematical Society} ,note= {To appear} ,series= dimacs ) @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( mat72a ,author= {David W. Matula} ,title= {The Employee Party Problem} ,journal= {Notices of the American Math Society} ,year= 1972 ,volume= 19 ,pages= {A-382} ,annote= {The expected size of the maximal clique} ) @article( mat72b ,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} ) @inproceedings( mato81 ,author= {Udi Manber and Martin Tompa} ,title= {The Effect of Number of Hamiltionian Paths on the Complexity of a Vertex-Coloring Problem} ,booktitle= focs81 ,year= 1981 ,pages= {220--227} ,organization= {IEEE} ,address= focs81a ,keywords= {hamiltonian path complexity} ) @article( mawe82 ,author= {A. J. Mansfield and D. J. A. Welsh} ,title= {Some colouring problems and their complexity} ,journal= adm ,year= 1982 ,volume= 13 ,pages= {159--170} ,keywords= {hajos non-3-colorable construction} ) @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= pitman ,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( mcd90a ,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( mcd90b ,author= {Colin McDiarmid} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {Colourings of Random Graphs} ,pages= {79--86} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {random graph theory} ,classif= {Random Graph Theory} ,annote= {A survey of results on total, edge and vertex colorings of random graphs} ) @article( mhr96 ,author= {M.V. Marathe nad H.B. Hunt III and S.S. Ravi} ,title= {Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs} ,journal= dam ,year= 1994 ,volume= 64 ,number= 2 ,pages= {135--149} ,keywords= {on-line domatic} ) @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( mipf90 ,author= {Matthias Middendorf and Frank Pfeiffer} ,title= {On the complexity of Recognizing Perfectly Orderable Graphs} ,journal= dm ,year= 1990 ,volume= 80 ,pages= {327--333} ,keywords= {chromatic theory} ,annote= {A note proving that recognizing perfectly orderable graphs is NP-complete} ) @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} ) @techreport( mor91 ,author= {Craig Morgenstern} ,title= {Improved Implementations of Dynamic Sequential Coloring Algorithms} ,institution= {Department of Computing Science, Texas Christian University} ,year= 1991 ,type= techrep ,number= {CoSc-91-1} ,month= apr ,note= {URL ftp://red.cs.tcu.edu/pub/morgenstern/} ,keywords= {Brelaz DSATUR RLF data structures } ,annote= {Use a special heap structure to improve running time of DSATUR to O(m) and Leighton's RLF to O(km)} ) @inproceedings( mor93 ,author= {Craig Morgenstern} ,title= {Distributed coloration neighborhood search} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,pages= {335--357} ,publisher= {American Mathematical Society} ,series= dimacs ,volume= 26 ) @article( more99 ,author= {Michael Molloy and Bruce Reed} ,title= {Critical subgraphs of a random graph} ,journal= {The Electronic Journal of Combinatorics} ,year= 1999 ,volume= 6 ,pages= {\#R35} ,note= {http://www.combinatorics.org/} ,keywords= {threshold, Gallai graphs} ) @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} ) @techreport( mpwz02 ,author= {R. Mulet and A. Pagnani and M. Weigt and R. Zecchina} ,title= {Coloring Random Graphs} ,institution= {arXiv.org} ,year= 2002 ,number= {cond-mat 0208460} ) @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( nero79 ,author= {Jaroslav Ne\u{s}et\u{r}il and Vojt\u{e}ch R\"{o}dl} ,title= {A Short Proof of the Existence of Highly Chromatic Hypergraphs withut Short Cycles} ,journal= jctsb ,year= 1979 ,volume= 27 ,pages= {225--227} ,keywords= {girth hypergraph} ,annote= {Proof uses Hypergraph construction } ) @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 ,address= longmana ,year= 1990 ,series= pitman ,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= {} ) @inproceedings( piur92 ,author= {Toniann Pitassi and Alas Urquhart} ,title= {The complexity of the Haj\'{o}s calculus} ,booktitle= focs92 ,year= 1992 ,pages= {187--196} ,keywords= {hajos non-3-colorable construction} ) @article( pre95 ,author= {J. Preater} ,title= {A passage time for greedy-coloring cycles} ,journal= {Random Structures and Algorithms} ,year= 1995 ,volume= 6 ,number= 1 ,pages= {105--111} ,keywords= {cycle third color} ) @incollection( pre98 ,author= {Steven Prestwich } ,title= { Using an incomplete version of dynamic backtracking for graph colouring} ,booktitle= {CP98 Workshop on Large Scale Combinatorial Optimisation and Constraints} ,publisher= {ELSEVIER} ,year= 1998 ,editor= {Mark Wallace and Yves Caseau and Eric Jacquet-Lagreze and Helmut Simonis and Gilles Pesant} ,note= {http://www.elsevier.nl:80/cas/tree/store/disc/free/endm/menu.sht} ,series= {Electronic Notes in Discrete Mathematics} ,volume= 1 ) @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} ) @Incollection{RDSBZ98, author = "Barry Rising and Max van Daalen and John Shawe-Taylor and Pete Burge and Janez Zerovnik", title = "A Neural Accelerator for Graph Colouring Based on an Edge Adding Technique", booktitle = "Proceedings of Neural Computation NC'98", publisher = "Technical University of Vienna", pages = "652--656", year = "1998" } @inproceedings( reg03 ,author= {Jean-Charles R\'{e}gin} ,title= {Solving the Maximum Clique Problem with Constraint Programming} ,booktitle= {Proceedings CPAIOR'03, Fifth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems} ,year= 2003 ,url = {http://www.crt.umontreal.ca/cpaior/} ) @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( rya95 ,author= {Jennifer Ryan} ,title= {The depth and width of local minima in descrete solution spaces} ,journal= dam ,year= 1995 ,volume= 56 ,number= 1 ,pages= {75--82} ,keywords= {local minima discrete solution space} ) @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( san90 ,author= {Laura A. Sanchis} ,title= {On the Complexity of Test Case Generation for {NP}-hard Problems} ,journal= ipl ,year= 1990 ,volume= 36 ,pages= {135--140} ,keywords= {related to vertex cover} ) @inproceedings( san92 ,author= {Laura A. Sanchis} ,title= {Generating Test Cases for the Vertex Cover Problem} ,booktitle= {Proceedings of the {DIMACS} Workshop on Computational Support for Discrete mathematics} ,month= mar ,year= 1992 ,note= {Technical Report received as Postscript} ) @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 74 (Proceedings of IFIP Congress, Stockholm, Sweden, August, 1974)} ,year= 1974 ,editor= {J. L. Rosenfeld} ,pages= {516--520} ,publisher= nh ,keywords= {timetable} ) @article( scst80 ,author= {G. Schmidt and T. Str\"{o}hlein} ,title= {Timetable Construction---{A}n Annotated Bibliography} ,journal= tcj ,year= 1980 ,volume= 23 ,number= 4 ,pages= {307--316} ,keywords= {graph color} ,classif= {Coloring Applications--Timetable} ) @inproceedings( sew93 ,author= {E. C. Sewell} ,title= {An improved algorithm for exact coloring} ,booktitle= {Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993} ,year= 1996 ,editor= {David S. Johnson and Michael A. Trick} ,pages= {359--373} ,publisher= {American Mathematical Society} ,series= dimacs ,volume= 26 ) @article( sey90 ,author= {P.D. Seymour} ,title= {Colouring series-parallel graphs} ,journal= comb ,year= 1990 ,volume= 10 ,number= 4 ,pages= {379--392} ,keywords= {series parallel graphs} ) @article( sha49 ,author= {Claude E. Shannon} ,title= {A Theorem on Coloring the Lines of a Network} ,journal= {Journal of Mathematics and Physics} ,year= 1949 ,volume= 28 ,pages= {148--151} ,keywords= {graph coloring} ) @article( shn84 ,author= {A. A. Shneider} ,title= {Classification Analysis of Heuristic Algorithms for Graph Coloring} ,journal= {Cybernetics} ,year= 1984 ,volume= 20 ,number= 4 ,pages= {484--492} ,note= {Translated from Kibernetika, No. 4, pp. 15--22, July--August, 1984} ,keywords= {graph color heuristic algorithms survey} ) @article( shsp87 ,author= {Eli Shamir and J. Spencer} ,title= {Sharp Concentration of the Chromatic Number of Random Graphs {$G_{n,p}$}} ,journal= comb ,year= 1987 ,volume= 7 ,number= 1 ,pages= {121--129} ,keywords= {graph color} ) @article( shup84 ,author= {Eli Shamir and Eli Upfal} ,title= { Sequential and Distributed Graph Coloring Algorithms with Performance Analysis in Random Graph Spaces} ,journal= joa ,year= 1984 ,volume= 5 ,number= 4 ,pages= {488--501} ,mrnumbers= { 86g#68077} ,classif= {Random Graphs and Chromatic Number} ) @incollection( sim85 ,author= {Gustavus J. Simmons} ,title= {The {O}chromatic Number of Planar Graphs} ,booktitle= {Graphs and Applications (Proceedings of the First Colorado Symposium on Graph Theory, 1982)} ,year= 1985 ,editor= {Frank Harary and John S. Maybee} ,pages= {295--316} ,publisher= wiley ,address= {New York} ,keywords= {graph coloring related theory} ,classif= {Generalized Coloring} ) @article( sim90 ,author= {Hans Ulrich Simon} ,title= {On Approximate Solutions for Combinatorial Optimization Problems} ,journal= siamdm ,year= 1990 ,volume= 3 ,number= 2 ,month= may ,pages= {294--310} ,keywords= {graph color} ,mrnumbers= {91c#68058} ) @inproceedings ( slm92 ,author= { Bart Selman and Hector Levesque and David Mitchell } ,title= { A New Method for Solving Hard Satisfiability Problems } ,booktitle= { Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), San Jose, CA } ,year= 1992 ,pages= { 440--446 } ,keywords= {graph coloring related topics} ,classif= {Hard and Easy Coloring} ) @incollection( slu89 ,author= {Maciej Slusarek} ,title= {A coloring algorithm for interval graphs} ,booktitle= {Mathematical Foundations of Computer Science} ,year= 1989 ,pages= {471--480} ,keywords= {dynamic storage allocation algorithm interval} ,publisher= sv ,series= lncs ,volume= 379 ) @inproceedings{smgr95, author = "B.M. Smith and S.A. Grant", title = "Sparse Constraint Graphs and Exceptionally Hard Problems", booktitle = "Proceedings of IJCAI-95", pages = "646-651", year = 1995} @article( smi75 ,author= {Graham Smith} ,title= {On Maintenance of the Opportunity List for Class-Teacher Timetable Problems} ,journal= cacm ,year= 1975 ,volume= 18 ,number= 4 ,pages= {203--208} ,month= apr ,keywords= {timetable graph coloring} ) @article( snh76 ,author= {T. Sakaki and K. Nakashima and Y. Hattori} ,title= {Algorithms for Finding in the Lump Both Bounds of the Chromatic Number of a Graph} ,journal= tcj ,year= 1976 ,volume= 19 ,number= 4 ,pages= {329--332} ,keywords= {graph coloring} ) @techreport( soge93 ,author= {Patrick Soriano and Michel Gendreau} ,title= {Diversification Strategies in Tabu Search Algorithms for the Maximum Clique Problem} ,institution= {Center for Research in Transportation, university of Montreal} ,year= 1993 ,type= resrep ,number= {CRT-940} ,month= sep ) @article( spth91 ,author= {David Springer and D. E. Thomas} ,title= {New Methods for Coloring and Clique Partitioning in Data Path Allocation} ,journal= {Integration} ,year= 1991 ,volume= 12 ,pages= {267--292} ,keywords= {graph coloring clique} ) @article( spvi85 ,author= {Jeremy P. Spinrad and Gopalakrishnan Vijayan} ,title= {Worst Case Analysis of a Graph Coloring Algorithm} ,journal= dam ,year= 1985 ,volume= 12 ,number= 1 ,pages= {89--92} ,mrnumbers= {86j#05065} ,classif= {Coloring--Special Graphs/Antigraphs} ) @article( sta76 ,author= {Saul Stahl} ,title= {{$n$-Tuple} Colorings and Associated Graphs} ,journal= jctsb ,year= 1976 ,volume= 20 ,pages= {185--203} ,keywords= {graph coloring chromatic number} ) @article( sto73 ,author= {L. Stockmeyer} ,title= {Planar 3-Colorability is Polynomial Complete} ,journal= {ACM SIGACT News} ,year= 1973 ,volume= 5 ,number= 3 ,pages= {19--25} ,note= {NCPY} ,keywords= {graph coloring complexity} ) @article( stst91 ,author= {Gisbert Stoyan and Robert Stoyan} ,title= {Colouring the Discretization Graphs Arising in the Multigrid Method} ,journal= cmpmth ,year= 1991 ,volume= 22 ,number= 7 ,pages= {55--62} ,keywords= {graph coloring linear time algorithms} ) @incollection( sys83 ,author= {Maciej M. Sys{\l}o} ,title= {{NP}-Complete Problems on Some Tree-Structured Graphs: A Review} ,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= {342--353} ,publisher= {Trauner Verlag} ,keywords= {graph coloring} ) @article( sys89 ,author= {Maciej M. Sys{\l}o} ,title= {Sequential Coloring Versus {W}elsh-{P}owell Bound} ,journal= dm ,year= 1989 ,volume= 74 ,pages= {241--243} ,keywords= {sequential graph coloring chromatic number} ) @Incollection{SZ91, author = "Milan Sokli\v{c} and Janez Zerovnik", title = "Distributed simulation of coloring graph vertices", booktitle = "Proceedings of the 24th Annual Simulation Symposium", editor = "A.H.Routan", publisher = "IEEE", address = "New York", year = "1991", pages = "118-122", note = "ISBN 0-8186-2169-9" } @Incollection{SZ92a, author = "John Shawe-Taylor and Janez Zerovnik", title = "Boltzmann Machines with Finite Alphabet", booktitle = "Artificial Neural Networks 2", editor = "I.Aleksander and J.Taylor", publisher = "Elsevier Science Publishers B.V.", address = "Amsterdam", year = "1992", pages = "391-394", note = "(vol.1) ISBN 0-444-89488-8" } @Techreport{SZ92b, author = "John Shawe-Taylor and Janez Zerovnik", title = "Generalised Boltzmann Machines", institution = "University of London, Royal Holloway and Bedford New College", year = "1992", number = "CSD-TR-92-29" } @Article{SZ95, author = "John Shawe-Taylor and Janez Zerovnik", title = "Analysis of the Mean Field Annealing Algorithm for Graph Colouring", journal = "Journal of Artificial Neural Networks", volume = "2", pages = "329--340", year = "1995" }%(special issue: Neural Networks for Optimization) @article( szwi68 ,author= {G. Szekeres and Herbert S. Wilf} ,title= {An Inequality for the Chromatic Number of a Graph} ,journal= jct ,year= 1968 ,volume= 4 ,number= 1 ,pages= {1--3} ,keywords= {graph color} ) @article( tar85 ,author= {Robert E. Tarjan} ,title= {Decomposition by Clique Separators} ,journal= dm ,year= 1985 ,volume= 55 ,number= 2 ,pages= {221--232} ,keywords= {graph color} ,mrnumbers= { 87i#05134} ) @article( tatr77 ,author= {Robert E. Tarjan and Anthony E. Trojanowski} ,title= {Finding a Maximum Independent Set} ,journal= sicomp ,year= 1977 ,volume= 6 ,number= 3 ,month= sep ,pages= {537--546} ,classif= {Cliques and Independent Sets} ) @article( thle81 ,author= {J. Thepot and G. Lechenault} ,title= { A Note on an Application of Hierarchical Clustering to Graph Coloring} ,journal= {RAIRO Rech. Oper.} ,year= 1981 ,volume= 15 ,number= 1 ,pages= {73--83} ,note= {French} ) @incollection( tof90 ,author= {Bjarne Toft} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {75 Graph-colouring Problems} ,pages= {0--35} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {graph theory problems} ,annote= {A collection of graph coloring problems relating to the theory of graphs. } ) @article( tom68 ,author= {I. Tomescu} ,title= {Sur le Probl\`{e}me du Coloriage des Graphes G\'{e}n\'{e}ralis\'{e}s} ,journal= {C. R. Acad. Sci. Paris Ser. A} ,year= 1968 ,volume= 267 ,pages= {250--252} ,keywords= {graph coloring} ) @article( tuc75 ,author= {Alan Tucker} ,title= {Coloring a family of circular arcs} ,journal= {SIAM Journal on Applied Mathematics} ,year= 1975 ,volume= 29 ,number= 3 ,pages= {493--502} ,month= {November} ,keywords= {coloring circular arc arcs} ) @article( tuc77 ,author= {Alan Tucker} ,title= {Critical perfect graphs and perfect 3-chromatic graphs} ,journal= jctsb ,year= 1977 ,volume= 23 ,pages= {143--149} ,keywords= {antiblocking polyhedra perfect graphs clique-generated} ) @article( tuc83 ,author= {Alan Tucker} ,title= {Uniquely Colorable Perfect Graphs} ,journal= dm ,year= 1983 ,volume= 44 ,pages= {187--194} ,keywords= {orderable graphs} ,annote= {defines sequential coloring - looks like a good reference to the Turner and Kucera easy k-color papers} ) @article( tur54 ,author= {P. Turan} ,title= {On the Theory of Graphs} ,journal= {Colloq. Math.} ,year= 1954 ,volume= 3 ,pages= {19--30} ,keywords= {some clique properties of graphs} ) @article( tur67 ,author= {Jonathan S. Turner} ,title= {Point Symmetric Graphs with a Prime Number of Points} ,journal= jct ,year= 1967 ,volume= 3 ,pages= {136--145} ,keywords= {graph coloring related topics special graphs} ) @inproceedings( tur84 ,author= {Jonathan S. Turner} ,title= {On the Probable Performance of Graph Coloring Algorithms} ,booktitle= {Proceedings of the 1984 Allerton Conference on Communication, Control and Computing} ,year= 1984 ,pages= {281--290} ,keywords= {graph coloring} ) @article( tur88 ,author= {Jonathan S. Turner} ,title= {Almost all $k$-Colorable Graphs are Easy to Color} ,journal= joa ,year= 1988 ,volume= 9 ,pages= {63--82} ,keywords= {graph color} ,classif= {Hard and Easy Coloring} ) @article( tuz92 ,author= {Zsolt Tuza} ,title= {Graph Coloring in Linear Time} ,journal= jctsb ,year= 1992 ,volume= 55 ,pages= {236--243} ,keywords= {graph coloring linear algorithm polynomial algorithm chromatic number} ) @incollection( veg84 ,author= {de la Vega, W. Fernandez} ,title= {On the Chromatic Number of Sparse Random Graphs} ,booktitle= {Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference---A Volume in Honour of {P}aul {E}rd\"{o}s} ,publisher= ap ,year= 1984 ,editor= {B\'{e}la Bollob\'{a}s} ,pages= {321--328} ,keywords= {graph color} ,classif= {Random Graphs and Chromatic Number} ) @incollection( veg85a ,author= {de la Vega, W. Fernandez} ,editor= {Micha{\l} Karo\'{n}ski and Andrzej Ruci\'{n}ski} ,title= {Random Graphs Almost Optimally Colorable in Polynomial Time} ,booktitle= {Random Graphs '83} ,publisher= nh ,address= {Amsterdam} ,year= 1985 ,pages= {311-317} ,keywords= {graph color} ,series= adm ,volume= 28 ,classif= {Hard and Easy Coloring} ) @inproceedings( vele88 ,author= {Ramarathnam Venkatesan and Leonid A. Levin} ,title= {Random Instances of a Graph Coloring Problem are Hard} ,booktitle= stoc88 ,year= 1988 ,pages= {217--222} ,keywords= {graph coloring random graphs theory} ,classif= {Coloring--Complexity Results} ) @article( vis92 ,author= {Sundar Vishwanathan} ,title= {Randomized Online Graph Coloring} ,journal= joa ,year= 1992 ,volume= 13 ,pages= {657--669} ,keywords= {graph coloring related theory} ,classif= {On-Line Coloring} ) @Article{VZ00, author = "Aleksander Vesel and Janez Zerovnik", title = "How good can ants color graphs?", journal = "Journal of computing and Information Technology - CIT", volume = "8", pages = "131--136", year = "2000" } @article( wag80 ,author= {S. Wagon} ,title= {A Bound on the Chromatic Number of Graphs without Certain Induced Subgraphs} ,journal= jctsb ,year= 1980 ,volume= 29 ,pages= {345-346} ,keywords= {graph coloring} ) @article( wan74 ,author= {Chung C. Wang} ,title= {An Algorithm for the Chromatic Number of a Graph} ,journal= jacm ,year= 1974 ,volume= 21 ,number= 3 ,pages= {385--391} ,keywords= {graph color} ,month= jul ,classif= {Coloring Algorithms--Exact} ) @article( wehe88 ,author= {D. de Werra and A. Hertz} ,title= {Consecutive Colorings of Graphs} ,journal= {Zeitshrift f\"{u}r Operations Research} ,year= 1988 ,volume= 32 ,number= 1 ,pages= {1--8} ,keywords= {graph coloring chromatic number} ) @article( wepo67 ,author= {D. J. A. Welsh and M. B. Powell} ,title= {An Upper Bound for the Chromatic Number of a Graph and Its Applications to Timetabling Problems} ,journal= tcj ,year= 1967 ,volume= 10 ,pages= {85--86} ,keywords= {graph color} ,classif= {Coloring Algorithms--Heuristic} ) @article( wer74 ,author= {D. de Werra} ,title= {Some Results in Chromatic Scheduling} ,journal= {Zeitschrift f\"{u}r Operations Research, Serie A} ,year= 1974 ,volume= 18 ,pages= {167--175} ,keywords= {graph coloring scheduling school timetable} ) @incollection( wer75a ,author= {D. de Werra} ,title= {A Few Remarks on Chromatic Scheduling} ,booktitle= {Combinatorial Programming: Methods and Applications} ,year= 1975 ,editor= {B. Roy} ,pages= {337--342} ,series= nastic ,publisher= {D. Reidel Publishing Company} ,address= {Dordrecht, Holland} ,volume= 19 ,keywords= {graph coloring application scheduling} ) @incollection( wer75b ,author= {D. de Werra} ,title= {How to Color a Graph} ,booktitle= {Combinatorial Programming: Methods and Applications} ,year= 1975 ,editor= {B. Roy} ,pages= {305--325} ,series= nastic ,publisher= {D. Reidel Publishing Company} ,address= {Dordrecht, Holland} ,volume= 19 ,keywords= {graph coloring} ) @article( wer75c ,author= {D. de Werra} ,title= {On a Particular Conference Scheduling Problem} ,journal= {INFOR---Canadian Journal of Operational Research and Information Processing} ,year= 1975 ,volume= 13 ,number= 3 ,month= oct ,pages= {308--315} ,keywords= {graph coloring timetable} ) @article( wer85 ,author= {D. de Werra} ,title= {An introduction to Timetabling} ,journal= ejor ,year= 1985 ,volume= 19 ,number= 2 ,pages= {151--162} ,keywords= {graph coloring application} ) @article( wer88 ,author= {D. de Werra} ,title= {Some Models of Graphs for Scheduling Sports Competitions} ,journal= dam ,year= 1988 ,volume= 21 ,number= 1 ,pages= {47--65} ,keywords= {scheduling} ) @incollection( wer90 ,author= {D. de Werra} ,title= {Heuristics for Graph Coloring} ,booktitle= {Computational Graph Theory} ,year= 1990 ,editor= {G. Tinhofer and E. Mayr and H. Noltemeier} ,pages= {191--208} ,publisher= sv ,address= sva ,series= {Computing, Supplement} ,volume= 7 ,keywords= {graph coloring heuristics tabu search sequential coloring} ) @incollection( whtu75 ,author= {Hassler Whitney and W. T. Tutte} ,title= {Kempe Chains and the Four Colour Problem} ,booktitle= {Studies in Graph Theory. Part II} ,publisher= {Mathematical Association of America} ,year= 1975 ,editor= {D. R. Fulkerson} ,pages= {378--413} ,keywords= {four color problem Kempe chains} ,series= {Mathematical Association of America Studies in Mathematics} ,volume= 12 ) @inproceedings( wig82 ,author= {Avi Wigderson} ,title= {A New Approximate Graph Coloring Algorithm} ,booktitle= stoc82 ,year= 1982 ,pages= {325--329} ,keywords= {graph coloring approximation algorithm} ) @article( wig83 ,author= {Avi Wigderson} ,title= {Improving the Performance Guarantee for Approximate Graph Coloring} ,journal= jacm ,year= 1983 ,volume= 30 ,number= 4 ,pages= {729--735} ,month= oct ) @inproceedings( wiho92 ,author= {Colin P. Williams and Tad Hogg} ,title= {Using Deep Structure to Locate Hard Problems} ,booktitle= {Proc. of AAAI92} ,year= 1992 ,pages= {472--477} ,publisher= {AAAI Press} ,address= {Menlo Park, CA} ) @inproceedings( wiho93 ,author= {Colin P. Williams and Tad Hogg} ,title= {Extending Deep Structure} ,booktitle= {Proc. of AAAI93} ,year= 1993 ,pages= {152--157} ,publisher= {AAAI Press} ,address= {Menlo Park, CA} ) @article( wil67 ,author= {Herbert S. Wilf} ,title= {The Eigenvalues of a Graph and its Chromatic Number} ,journal= {J. London math. Soc.} ,year= 1967 ,volume= 42 ,pages= {330--332} ,keywords= {graph color} ) @incollection( wil70 ,author= {M. R. Williams} ,title= {The Colouring of Very Large Graphs} ,booktitle= {Combinatorial Structures and Their Applications: Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications} ,publisher= {Gordon and Breach} ,address= {New York} ,year= 1970 ,editor= {Richard Guy and Haim Hanani and Norbert Sauer and Johanen Schonheim} ,pages= {477--478} ,keywords= {graph color} ,classif= {Coloring Algorithms--Heuristic} ) @incollection( wil71 ,author= {Herbert S. Wilf} ,title= {An Analogue of the Chromatic Polynomial for Vertex Assignments Modulo 3} ,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= {311--313} ,publisher= ap ,address= {London} ,keywords= {graph coloring} ) @article( wil76 ,author= {John Wilson} ,title= {New Light on the Origin of the Four-Color Conjecture (Letter)} ,journal= {Historia Mathematica} ,year= 1976 ,volume= 3 ,pages= {329--330} ,keywords= {four color problem} ) @article( wil84 ,author= {Herbert S. Wilf} ,title= {Backtrack: An {$O(1)$} Expected Time Algorithm for the Graph Coloring Problem} ,journal= ipl ,year= 1984 ,volume= 18 ,number= 3 ,month= mar ,pages= {119--121} ,keywords= {analysis } ,mrnumbers= { 86c#68036} ,classif= {Theoretical} ) @article( wil86 ,author= {Herbert S. Wilf} ,title= {Spectral Bounds for the Clique and Independence Numbers of Graphs} ,journal= jctsb ,year= 1986 ,volume= 40 ,number= 1 ,pages= {113--117} ,keywords= {graph coloring related clique theory} ) @incollection( wil90 ,author= { Brian Wilson} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {Line-distinguishing and Harmonious Colourings} ,pages= {115--133} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {theory generalized colorings } ,classif= {Theory related} ) @article( woo68 ,author= {D. C. Wood} ,title= {A System for Computing University Examination Timetables} ,journal= tcj ,year= 1968 ,volume= 11 ,pages= {41--47} ,keywords= {graph coloring related} ,classif= {Coloring Applications--Timetable} ) @article( woo69 ,author= {D. C. Wood} ,title= {A Technique for Colouring a Graph Applicable to Large Scale Timetabling Problems} ,journal= tcj ,year= 1969 ,volume= 12 ,pages= {317--319} ,keywords= {graph color} ,classif= {Coloring Algorithms--Heuristic} ) @incollection( woo90 ,author= {Douglas Woodall} ,editor= {Roy Nelson and Robin J. Wilson} ,booktitle= {Graph Colourings} ,title= {Improper Colourings of Graphs} ,pages= {45--63} ,publisher= longman ,year= 1990 ,series= pitman ,address= longmana ,keywords= {conflicts} ,classif= {Generalized Coloring, Theory} ,annote= {Theoretical results related to generalizations of edgeless graphs. Vertex and edge colorings considered. An $(m,d)*$-coloring of $G$ corresponds to a partitioning of the vertices into $m$ parts each of which has induced degree of at most $sd$.} ) @article( wood97 ,author= {David R. Wood} ,title= {An algorithm for finding a maximum clique in a graph} ,journal= {Operations Research Letters} ,year= 1997 ,volume= 21 ,pages= {211--217} ,keywords= {graph algorithm maximum clique problem} ) @incollection( wowi78 ,author= {D. R. Woodall and Robin J. Wilson} ,title= {The {A}ppel-{H}aken Proof of the Four Color Theorem} ,booktitle= {Selected Topics in Graph Theory} ,publisher= ap ,chapter= 4 ,year= 1978 ,editor= {Lowell W. Beineke and Robin J. Wilson} ,pages= {83--101} ,address= {London} ,keywords= {graph color} ,classif= {Four-Color Problem} ) @unpublished( yan92 ,author= {Mihalis Yannakakis} ,title= {On the Approximation of Maximum Satisfiability} ,howpublished= {Personal Communication} ,year= 1992 ,note= {A preliminary version of this work was presented at the Third Annual ACM-SIAM Symposium on discrete Algorithms} ,keywords= {polynomial algorithm} ) @booklet( yeh89 ,title= { Odd Cycles, Bipartite Subgraphs, and Approximate Graph Coloring} ,author= {S. S. W. Yeh} ,howpublished= {Publ: Princeton University, Princeton, NJ} ,year= 1989 ,note= {UMI order no: GAX89-17763} ) @incollection( you70 ,author= {J. W. T. Youngs} ,title= {Remarks on the Four Color Problem} ,booktitle= {Combinatorial Structures and Their Applications: Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications} ,year= 1970 ,editor= {Richard Guy and Haim Hanani and Norbert Sauer and Johanan Schonheim} ,pages= {479--480} ,publisher= {Gordon and Breach} ,address= {New York} ,keywords= {graph coloring related theory} ,classif= {Four-Color Problem} ) @article( zas82 ,author= {T. Zaslavsky} ,title= {Signed Graph Coloring} ,journal= dm ,year= 1982 ,volume= 39 ,number= 2 ,pages= {215--228} ) @Article{zer00, author = "Janez Zerovnik", title = "On Temperature Schedules for Generalized Boltzmann Machine", journal = "Neural Network World", volume = "3", pages = "495-503", year = "2000" } @article( zer89a ,author= {Janez \v{Z}erovnik} ,title= {A Randomised Heuristical Algorithm for Estimating the Chromatic Number of a Graph} ,journal= ipl ,year= 1989 ,volume= 33 ,number= 4 ,pages= {213--219} ,keywords= {graph color} ,annote= {Various antivoter heuristics are presented with experimental results.} ,classif= {Coloring Algorithms--Heuristic} ) @incollection( zer89b ,author= {Janez \v{Z}erovnik} ,title= {A Randomised Heuristical Algorithm for Graph Colouring} ,booktitle= {Graph Theory (Proceedings of the Eighth Yugoslav Seminar on Graph Theory, Novi Sad, April, 1987)} ,year= 1989 ,editor= {R. To\v{s}i\'{c} and D. Acketa and V. Petrovi\'{c} and R. Doroslova\v{c}ki} ,pages= {137--147} ,publisher= {Institute of Mathematics} ,address= {University of Novi Sad, Yugoslavia} ,keywords= {graph coloring antivoter algorithm} ) @article( zer90 ,author= {Janez \v{Z}erovnik} ,title= {A Parallel Variant of a Heuristical Algorithm for Graph Colouring} ,journal= parcmp ,year= 1990 ,volume= 13 ,pages= {95--100} ,classif= {Planar/Parallel Coloring} ) @Article{zer93, author = "Janez Zerovnik", title = "Regular Graphs are 'Difficult' for Colouring", journal = "Informatica", volume = "17", pages = "59--63", year = "1993" } @Article{zer94, author = "Janez Zerovnik", title = "A Randomized Algorithm for $k$--colorability", journal = "Discrete Mathematics", volume = "131", pages = "379--393", year = "1994" } @Incollection{zer99, author = "Janez Zerovnik", title = "Deriving formulas for domination numbers of fasciagraphs and rotagraphs", editor = "G.Ciobanu and G.Paun", booktitle = "12th International Symposium on Fundamentals of Computation Theory", series = "Lecture notes in computer science, 1684", publisher = "Springer", address = "Berlin", year = "1999", pages = "559-568" } @article( zhu85 ,author= {Ao Xin Zhu} ,title= {Non-Coloring-Contradiction Graphs and a Graph Coloring Algorithm} ,journal= cjc ,year= 1985 ,volume= 8 ,number= 3 ,pages= {189--197} ,note= {Chinese: English summary} ,keywords= {graph color} ,mrnumbers= {87g#05102} ) @Article{ZK92, author = "Janez Zerovnik and Matja\v{z} Kaufman", title = "A parallel variant of a heuristical algorithm for graph coloring - corrigendum", journal = "Parallel Computing", volume = "18", pages = "1992", year = "897-900" } @article( zky49 ,author= {A. A. Zykov} ,title= {On Some Properties of Linear Complexes} ,journal= {Matematicheskii Sbornik} ,year= 1949 ,volume= 24 ,pages= {163--188} ,note= {English Trans. Amer. Soc. Translation no. 79, 1952} ,keywords= {graph color} )