@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{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{fundi = {Fundamenta Informaticae}} @string{fundm = {Fundamenta Mathematicae}} @string{geom = {Proceedings of the Annual Symposium on Computational Geometry}} @string{geom85 = {Proceedings of the First Annual Symposium on Computational Geometry}} @string{geom85a = {Baltimore, Maryland}} @string{geom85v = {1}} @string{geom86 = {Proceedings of the Second Annual Symposium on Computational Geometry}} @string{geom86a = {Yorktown Heights, New York}} @string{geom86v = {2}} @string{geom87 = {Proceedings of the Third Annual Symposium on Computational Geometry}} @string{geom87a = {Waterloo, Ontario}} @string{geom87v = {3}} @string{geom88 = {Proceedings of the Fourth Annual Symposium on Computational Geometry}} @string{geom88a = {Urbana-Champaign, Illinois}} @string{geom88v = {4}} @string{hd = {Holden-Day, Inc.}} @string{hda = {San Francisco, California}} @string{iac = {Information and Computation}} @string{ic = {Information and Control}} @string{icalp = {International Colloquium on Automata, Languages, and Programming}} @string{icalp72 = {1st International Colloquium on Automata, Languages, and Programming}} @string{icalp72a = {Paris, France}} @string{icalp72v = {1}} @string{icalp74 = {2nd International Colloquium on Automata, Languages, and Programming}} @string{icalp74a = {Saarbr\"ucken, Germany}} @string{icalp74v = {2}} @string{icalp76 = {3rd International Colloquium on Automata, Languages, and Programming}} @string{icalp76a = {Edinburgh, Great Britain}} @string{icalp76v = {3}} @string{icalp77 = {4th International Colloquium on Automata, Languages, and Programming}} @string{icalp77a = {Turku, Finland}} @string{icalp77v = {4}} @string{icalp78 = {5th International Colloquium on Automata, Languages, and Programming}} @string{icalp78a = {Udine, Italy}} @string{icalp78v = {5}} @string{icalp79 = {6th International Colloquium on Automata, Languages, and Programming}} @string{icalp79a = {Gras, Austria}} @string{icalp79v = {6}} @string{icalp80 = {7th International Colloquium on Automata, Languages, and Programming}} @string{icalp80a = {Noordwijkerhout, The Netherlands}} @string{icalp80v = {7}} @string{icalp81 = {8th International Colloquium on Automata, Languages, and Programming}} @string{icalp81a = {Haifa, Israel}} @string{icalp81v = {8}} @string{icalp82 = {9th International Colloquium on Automata, Languages, and Programming}} @string{icalp82a = {Aarhus, Denmark}} @string{icalp82v = {9}} @string{icalp83 = {10th International Colloquium on Automata, Languages, and Programming}} @string{icalp83a = {Barcelona, Spain}} @string{icalp83v = {10}} @string{icalp84 = {11th International Colloquium on Automata, Languages, and Programming}} @string{icalp84a = {Antwerp, Belgium}} @string{icalp84v = {11}} @string{icalp85 = {12th International Colloquium on Automata, Languages, and Programming}} @string{icalp85a = {Nafplion, Greece}} @string{icalp85v = {12}} @string{icalp86 = {13th International Colloquium on Automata, Languages, and Programming}} @string{icalp86a = {Rennes, France}} @string{icalp86v = {13}} @string{icalp87 = {14th International Colloquium on Automata, Languages, and Programming}} @string{icalp87a = {Karlsruhe, Germany}} @string{icalp87v = {14}} @string{icalp88 = {15th International Colloquium on Automata, Languages, and Programming}} @string{icalp88a = {?}} @string{icalp88v = {15}} @string{icr = {Institute for Computer Research}} @string{icss = {International Computer Science Series}} @string{ieeetec = {IEEE Transactions on Electronic Computers}} @string{ieeetit = {IEEE Transactions on Information Theory}} @string{ifip71 = {Proceedings of IFIP Congress 71, Foundations of Information Processing}} @string{ijcis = {International Journal of Computer and Information Sciences}} @string{ijcm = {International Journal of Computer Mathematics}} @string{ije = {International Journal of Electronics}} @string{ijm = {Illinois Journal of Mathematics}} @string{ijtp = {International Journal of Theoretical Physics}} @string{inprep = {in preparation}} @string{inpress = {in press}} @string{ists59 = {Proceedings of the International Symposium on the Theory of Switching, Part II}} @string{ists59a = {Cambridge, Massachusetts}} @string{jams = {Journal of Australian Mathematics Society}} @string{jct = {Journal of Combinatorial Theory}} @string{jctsa = {Journal of Combinatorial Theory Series A}} @string{jctsb = {Journal of Combinatorial Theory Series B}} @string{jgt = {Journal of Graph Theory}} @string{jnt = {Journal of Number Theory}} @string{joa = {Journal of Algorithms}} @string{joc = {Journal of Complexity}} @string{jsl = {The Journal of Symbolic Logic}} @string{linalg = {Linear Algebra and its Applications}} @string{lmps64 = {Proceedings of the 1964 International Congress on Logic, Methodology, and Philosophy of Science}} @string{lncs = {Lecture Notes in Computer Science}} @string{lnems = {Lecture Notes in Economics and Mathematical Systems}} @string{lnm = {Lecture Notes in Mathematics}} @string{manual = {Manual}} @string{manuscr = {unpublished manuscript}} @string{mapol = {Mathesis Polska}} @string{matcomp = {Mathematics of Computation}} @string{mathann = {Mathematische Annalen}} @string{mathmag = {Mathematics Magazine}} @string{matpgm = {Mathematical Programming}} @string{mpcps = {Mathematical Proceedings of the Cambridge Philosophical Society}} @string{nacs2 = {NATO Conference Series II: Systems Science}} @string{nams = {Notices of the American Mathematical Society}} @string{nascib = {NATO Advanced Science Institute Series B: Physics}} @string{nascic = {NATO Advanced Science Institute Series C: Mathematical and Physical Sciences}} @string{nascie = {NATO Advanced Science Institute Series E: Applied Sciences}} @string{nascif = {NATO Advanced Science Institute Series F: Computer and System Sciences}} @string{nastic = {NATO Advanced Study Institute Series C: Mathematical and Physical Sciences}} @string{nastid = {NATO Advanced Study Institute Series D: Behavioural and Social Sciences}} @string{nh = {North-Holland Publishing Co.}} @string{nha = {Amsterdam}} @string{nmor = {National Meeting of the Operations Research Society of America}} @string{nmor59 = {16th National Meeting of the Operations Research Society of America}} @string{nmor59a = {Pasadena, California}} @string{nmor59v = {16}} @string{nrlq = {Naval Research Logistics Quarterly}} @string{nyas = {Annals of the New York Academy of Sciences}} @string{order = {Order}} @string{pams = {Proceedings of the American Mathematical Society}} @string{parcmp = {Parallel Computing}} @string{perscom = {personal communication}} @string{ph = {Prentice-Hall, Inc.}} @string{pha = {Englewood Cliffs, New Jersey}} @string{pjm = {Pacific Journal of Mathematics}} @string{qam = {Quarterly of Applied Mathematics}} @string{resrep = {Research Report}} @string{reston = {Reston Publishing Co.}} @string{restona = {Reston, Virginia}} @string{sciamer = {Scientific American}} @string{siam = {Society for Industrial and Applied Mathematics}} @string{siamdm = {SIAM Journal on Discrete Mathematics}} @string{siamsp = {SIAM-AMS Proceedings}} @string{sigact = {ACM Special Interest Group on Automata and Computability Theory}} @string{sigactn = {ACM SIGACT News}} @string{sija = {SIAM Journal of Algorithms}} @string{sijadm = {SIAM Journal on Algebraic and Discrete Methods}} @string{sijam = {SIAM Journal on Applied Mathematics}} @string{sijco = {SIAM Journal on Control and Optimization}} @string{sijma = {SIAM Journal on Mathematical Analysis}} @string{sijna = {SIAM Journal on Numerical Analysis}} @string{sijssc = {SIAM Journal on Scientific and Statistical Computing}} @string{sirev = {SIAM Review}} @string{sisam = {SIAM Studies in Applied Mathematics}} @string{smp78 = {Sparse Matrix Proceedings 1978}} @string{smz = {Sibirski\u{\i} Matematicheski\u{\i} Zhurnal}} @string{spring = {Spring}} @string{stoc = {Proceedings of the Annual ACM Symposium on Theory of Computing}} @string{stoc69 = {Proceedings of the First Annual ACM Symposium on Theory of Computing}} @string{stoc69a = {Marina del Rey, California}} @string{stoc69v = {1}} @string{stoc70 = {Proceedings of the Second Annual ACM Symposium on Theory of Computing}} @string{stoc70a = {Northampton, Massachusetts}} @string{stoc70v = {2}} @string{stoc71 = {Proceedings of the Third Annual ACM Symposium on Theory of Computing}} @string{stoc71a = {Shaker Heights, Ohio}} @string{stoc71v = {3}} @string{stoc72 = {Proceedings of the Fourth Annual ACM Symposium on Theory of Computing}} @string{stoc72a = {Denver, Colorado}} @string{stoc72v = {4}} @string{stoc73 = {Proceedings of the Fifth Annual ACM Symposium on Theory of Computing}} @string{stoc73a = {Austin, Texas}} @string{stoc73v = {5}} @string{stoc74 = {Proceedings of the Sixth Annual ACM Symposium on Theory of Computing}} @string{stoc74a = {Seattle, Washington}} @string{stoc74v = {6}} @string{stoc75 = {Proceedings of the Seventh Annual ACM Symposium on Theory of Computing}} @string{stoc75a = {Albuquerque, New Mexico}} @string{stoc75v = {7}} @string{stoc76 = {Proceedings of the Eighth Annual ACM Symposium on Theory of Computing}} @string{stoc76a = {Hershey, Pennsylvania}} @string{stoc76v = {8}} @string{stoc77 = {Proceedings of the Ninth Annual ACM Symposium on Theory of Computing}} @string{stoc77a = {Boulder, Colorado}} @string{stoc77v = {9}} @string{stoc78 = {Proceedings of the Tenth Annual ACM Symposium on Theory of Computing}} @string{stoc78a = {San Diego, California}} @string{stoc78v = {10}} @string{stoc79 = {Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing}} @string{stoc79a = {Atlanta, Georgia}} @string{stoc79v = {11}} @string{stoc80 = {Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing}} @string{stoc80a = {Los Angeles, California}} @string{stoc80v = {12}} @string{stoc81 = {Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing}} @string{stoc81a = {Milwaukee, Wisconsin}} @string{stoc81v = {13}} @string{stoc82 = {Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing}} @string{stoc82a = {San Francisco, California}} @string{stoc82v = {14}} @string{stoc83 = {Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing}} @string{stoc83a = {Boston, Massachusetts}} @string{stoc83v = {15}} @string{stoc84 = {Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing}} @string{stoc84a = {Washington, D. C.}} @string{stoc84v = {16}} @string{stoc85 = {Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing}} @string{stoc85a = {Providence, Rhode Island}} @string{stoc85v = {17}} @string{stoc86 = {Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing}} @string{stoc86a = {Berkeley, California}} @string{stoc86v = {18}} @string{stoc87 = {Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing}} @string{stoc87a = {New York, New York}} @string{stoc87v = {19}} @string{stoc88 = {Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing}} @string{stoc88a = {Chicago, Illinois}} @string{stoc88v = {20}} @string{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{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( cl: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} ) @article( cl: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( cl:ahk ,author= {K. Appel and W. Haken and J. Koch} ,title= {Every planar map is four colorable: Part 2, Reducibility} ,journal= ijm ,year= 1977 ,volume= 21 ,pages= {491--567} ,keywords= {graph color} ) @article( cl:ani86 ,author= {Anisimov, A. V.} ,title= { Local optimization of graph coloring} ,journal= { Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskoi SSR. Kibernetika} ,year= 1986 ,number= 6 ,pages= {1--8,133} ,note= {number or volume?} ,keywords= {graph color} ,mrnumbers= {88k#05077} ,abstract= { A proper coloring of $G$ is a function $f\:V(G)\to\bf N$ such that if $(u,v)\in E(G)$ then $f(u)\not=f(v)$. The proper coloring $f$ of $G$ is locally optimal if for every $v\in V(G)$, $f(v)=\min\{{\bf N}-f(\Gamma(v))\}$ $(\Gamma(v)$ is the neighbourhood of $v$). The author studies the properties of locally optimal colorings. He proves, among other things, that the following inequality holds: $\beta\ge(k^2-3k+2)/2+n-e$, where $\beta$ is the vertex independence number of $G$, $n,e$ are the numbers of vertices and edges, respectively, and $k$ is the maximal number of colors in a locally optimal coloring. He also gives some sequential and parallel algorithms for a locally optimal coloring.} ) @article( cl:apha77 ,author= {K. Appel and W. Haken} ,title= {Every planar map is four colorable: Part 1, Discharging} ,journal= ijm ,year= 1977 ,volume= 21 ,pages= {429--490} ,keywords= {graph color} ) @techreport( cl: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} ) @article( cl:asgi84 ,author= {Bengt Aspvall and John R. Gilbert} ,title= { Graph coloring using eigenvalue decomposition} ,journal= sijadm ,year= 1984 ,volume= 5 ,number= 4 ,pages= {526--538} ,mrnumbers= { 86a#05044} ) @techreport( cl: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} ) @article( cl: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} ) @article( cl: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 ,pages= {1054--1068} ,keywords= {a algorithm based on triangulated graph properties} ) @article( cl:bedu84 ,author= {C. Berge and P. Duchet} ,title= {Strongly Perfect Graphs} ,journal= adm ,year= 1984 ,volume= 21 ,pages= {57--61} ,keywords= {graph coloring} ) @inbook( cl:ber78 ,author= {Claude Berge} ,title= {Algorithms and extremal problems for equipartite colorings in graphs and hypergraphs} ,pages= {149--150} ,publisher= nh ,year= 1978 ,volume= 2 ,series= adm ,keywords= {graph color} ) @article( cl: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} ) @article( cl:bewi85 ,author= { Bender, Edward A. and Wilf, Herbert S.} ,title= { A theoretical analysis of backtracking in the graph coloring problem} ,journal= joa ,year= 1985 ,volume= 6 ,number= 2 ,pages= {275--282} ,mrnumbers= { 86j#05057} ) @article( cl: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( cl:bksw90 ,author= {Jason I. Brown and David kelly and J. Schonheim and Robert E. Woodrow} ,title= { Graph coloring satisfying restraints} ,journal= dm ,year= 1990 ,volume= 80 ,number= 2 ,pages= {123--143} ,mrnumbers= {91c#05075} ) @inproceedings( cl:blu89 ,author= {Avrin 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 } ) @inproceedings( cl:blum90 ,author= {Avrim Blum} ,title= {Some Tools for Approximate 3-Coloring} ,booktitle= {31st Annual Symposium on Foundations of Computer Science} ,year= 1990 ,pages= {554--562} ,keywords= {graph coloring approximation algorithm} ) @inproceedings( cl:bms80 ,author= {E. Burattini and A. Massarotti and A. Santaniello} ,title= { A graph colouration technique} ,booktitle= {Second International Conference on Information Sciences and Systems (Univ. Patras, Patras, 1979), Vol. III} ,year= 1980 ,pages= {326--333} ,publisher= {Reidel} ,keywords= {graph color} ,mrnumbers= { 82g#05045} ) @article( cl: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} ) @inproceedings( cl:boha90 ,author= {Ravi Boppana and Magnus Halldorsson} ,title= {Approximating Maximum Independent Sets by Excluding Subgraphs} ,booktitle= {SWAT 90 2nd Scandinavian Workshop on Algorithm Theory} ,year= 1990 ,pages= {13--25} ,series= lncs ,volume= 3 ,keywords= {graph coloring related clique approximation complexity} ,abstract= {Guarantees $O(n/(log n)^2)$ approximation) } ) @article( cl: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} ) @article( cl:bol88 ,author= {B. Bollob\'{a}s} ,title= {The chromatic number of random graphs} ,journal= comb ,year= 1988 ,volume= 8 ,number= 1 ,pages= {49--55} ,keywords= {graph color} ) @article( cl:boll78 ,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} ) @article( cl: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} ) @incollection( cl:both85 ,author= {B\'{e}la Bollob\'{a}s and Andrew Thomason} ,title= {Random graphs of small order} ,booktitle= {Random Graphs '83} ,publisher= nh ,year= 1985 ,pages= {47--97} ,note= {Section 6: ``Colouring large random graphs''} ,keywords= {graph color} ,series= adm ,volume= 28 ) @article( cl: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( cl:brke73 ,author= {Coen Bron and Joep Kerbosch} ,title= {Algorithm 457: Finding all Cliques of an Undirected Graph} ,journal= cacm ,year= 1973 ,volume= 16 ,number= 9 ,pages= {575-577} ,keywords= {fgraph coloring related clique backtracking branch and bound} ) @article( cl:bro41 ,author= {R. L. Brooks} ,title= {On coloring the nodes of a network} ,journal= mpcps ,year= 1941 ,volume= 37 ,pages= {194--197} ,keywords= {graph color} ) @article( cl: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} ) @article( cl: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} ,note= {Part I.} ,keywords= {graph color} ) @article( cl:capa90 ,author= {R. Carraghan and P. 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} ) @article( cl: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( cl: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} ) @incollection( cl:cgj78 ,author= {V. Chv\'{a}tal and M. R. Garey and D. S. Johnson} ,title= {Two results concerning multicoloring} ,publisher= nh ,year= 1978 ,pages= {151--154} ,note= {booktitle?} ,keywords= {graph color} ,series= adm ,volume= 2 ) @inproceedings( cl: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} ,abstract= {The author considers the class $A_n$ of graphs composed from $n$ complete graphs with $n$ vertices each, such that any two different complete graphs have exactly one common vertex. Let $d(G)$ be the maximal number of complete graphs of $G$ having a common vertex. It is proved that the number $K(G)$ of vertices common to at least two complete graphs for every graph $G\in A_n$ such that $d(G)\leq n-1$ satisfies $n\leq K(G)\leq\binom n2$ and $K(G)=n$ if and only if $n=k^2+k+1$, $k\geq 2$, for every graph $G\in A_n$ such that $d(G)\leq n-2$, which follows easily from the theory of finite projective planes. A heuristic algorithm for coloring graphs from $A_n$ is proposed.} ) @article( cl:chhmw87 ,author= {V. Chv\'{a}tal and C. T. Hoang and N. V. R. Mahadev and D. de Werra} ,title= {Four Classes of Perfectly Orderable Graphs} ,journal= jgt ,year= 1987 ,volume= 11 ,pages= {481--495} ,keywords= {graph coloring related theory} ) @article( cl: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} ,abstract= {This paper is devoted to the complexity evaluation of exact coloring algorithms on graphs. A new method of implicit enumeration is described and is shown (both by complexity analysis and experiments) to be computationally superior to other existing methods.} ) @incollection( cl:chl88 ,author= {G. Campers and O. Henkes and J. P. Leclerq} ,title= {Graph coloring heuristics: a survey, some new propositions and computational experiences on random and ``{L}eighton's'' graphs} ,booktitle= { Operational research '87 (Buenos Aires, 1987) } ,publisher= nh ,year= 1988 ,pages= {917--932} ,mrnumbers= { 90d#05095} ) @article( cl:chr71 ,author= {N. Christofides} ,title= {An algorithm for the chromatic number of a graph} ,journal= comp ,year= 1971 ,volume= 14 ,pages= {38--39} ,keywords= {graph color} ) @article( cl:chsl84 ,author= {M. Chorbak and M. \'{S}lusarek} ,title= {Problem 84-23} ,journal= joa ,year= 1984 ,volume= 5 ,pages= {588} ,keywords= {related to graph coloring} ) @incollection( cl:chv84 ,author= {V. Chv\'{a}tal} ,title= {Perfectly Ordered Graphs} ,booktitle= {Topics on Perfect Graphs} ,publisher= nh ,year= 1984 ,editor= {C. Berge and V. Chv\'{a}tal} ,series= {Annals of Discrete Mathematics} ,keywords= { graph coloring related theory} ,volume= 21 ) @article( cl:chw87 ,author= { Chams, M. and Hertz, A. and de Werra, D.} ,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} ,abstract= {Methods of thermodynamical simulation have been used for several famous combinatorial optimization problems. For graph coloring (i.e., partition of the node set into as few independent sets as possible) we describe a method of simulation. Such an approach is combined with other techniques for graph coloring. Experiments on random graphs provide evidence that this combination gives better results than any one of the original noncombined methods} ) @inproceedings( cl: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} ) @article( cl: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} ,keywords= {graph color} ) @article( cl: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} ) @article( cl:como83 ,author= {T. F. Coleman and J. J. More} ,title= {Estimation of sparse Jacobian matrices and graph coloring problems} ,journal= sijna ,year= 1983 ,volume= 20 ,number= 1 ,pages= {187--209} ) @article( cl:como84 ,author= {Thomas F. Coleman and Jorge J. More} ,title= { Estimation of sparse Hessian matrices and graph coloring problems} ,journal= matpgm ,year= 1984 ,volume= 28 ,number= 3 ,pages= {243--270} ,mrnumbers= { 85d#65041} ) @article( cl: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} ) @techreport( cl:cul92a ,author= {Joseph C. Culberson} ,title= {Iterated Greedy Graph Coloring and the Difficulty Landscape} ,institution= ualtacs ,year= 1992 ,type= techrep ,number= {TR 92-07} ,address= {Edmonton, Alberta Canada T6G 2H1} ,note= {ftp ftp.cs.ualberta.ca pub/TechReports} ) @article( cl: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( cl:ddh84 ,author= {Peter Dencker and Karl Durre 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} ) @article( cl: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( cl:des54 ,author= {Blanches Descartes} ,title= {Solution to Advanced Problem 4526} ,journal= amm ,year= 1954 ,volume= 61 ,pages= {352} ,note= {proposed by P. Ungar; psuedonym for Tutte} ,keywords= {graph coloring theory girth} ) @inproceedings( cl:dhm82 ,author= {K. D\"{u}rre and J. Heuft and H. Muller} ,title= { Worst and best case behaviour of an approximate graph coloring algorithm} ,booktitle= { Proc. 7th conference on graphtheoretic concepts in computer science (Linz, Austria, June 15-17, 1981)} ,year= 1982 ,editor= {J. R. Muhlbacher and Carl Hansen Verlag} ,pages= {339-348} ,address= {Munich} ) @inproceedings( cl: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 } ,year= 1986 ,editor= {J. Gruska and B. Rovan and J. Wiedermann} ,pages= {273--282} ,publisher= sv ,series= lncs ,volume= 233 ,keywords= {graph color} ,mrnumbers= { 87m#68008} ) @article( cl:dir53 ,author= {G. A. Dirac} ,title= {The structure of k-chromatic Graphs} ,journal= fundm ,year= 1953 ,volume= 40 ,pages= {42--55} ,note= {color} ) @article( cl:dubr81 ,author= {R. D. Dutton and R. C. Brigham} ,title= {A new graph coloring algorithm} ,journal= tcj ,year= 1981 ,volume= 24 ,number= 1 ,pages= {85--86} ) @inproceedings( cl:dun76 ,author= {F. D. J. Dunstan} ,title= {Sequential colourings of graphs} ,booktitle= {Proceedings of Fifth British Combinatorial Conference} ,year= 1976 ,pages= {151--158} ,publisher= {Utilitas Mathematica} ,keywords= {graph color} ) @incollection( cl:dur73 ,author= {K. D\"{u}rre} ,title= {An algorithm for coloring the vertices of an arbitrary graph} ,booktitle= {unknown} ,publisher= sv ,year= 1973 ,editor= {P. Deussen} ,pages= {82--89} ,keywords= {graph color} ,series= lnems ,volume= 78 ) @inproceedings( cl:dyfr86 ,author= {M. E. Dyer and A. M. Frieze} ,title= {Fast Solution of Some Random {NP}-hard Problems} ,booktitle= focs86 ,year= 1986 ,pages= {331--336} ,keywords= {graph coloring related theory} ) @article( cl: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} ) @phdthesis( cl:ear68 ,author= {S. Early} ,title= {Evaluating a Timetabling Algorithm Based on Graph Recolouring} ,school= {University of Oxford} ,year= 1968 ,note= {B. Phil. Diss.} ) @article( cl:elle89 ,author= {J. A. Ellis and P. M. Lepolesa} ,title= {A {L}as {V}egas coloring algorithm} ,journal= tcj ,year= 1989 ,volume= 32 ,number= 5 ,pages= {474--476} ,keywords= {graph color} ) @article( cl: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( cl: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( cl:erwi77 ,author= {P. Erd\"{o}s and R. J. Wilson} ,title= {On the chromatic index of almost all graphs} ,journal= jctsb ,year= 1977 ,volume= 23 ,pages= {255--257} ,keywords= {graph color} ) @inproceedings( cl:femo91 ,author= {Feder and Motwani} ,title= {Clique Partitions, Graph Compression and Speeding Up Algorithms} ,booktitle= {Proceedings of the Twenty Third Annual Symposium on Theory of Computing} ,year= 1991 ,pages= {123--3} ,keywords= {graph coloring related topics} ) @inproceedings( cl:fglss91 ,author= {U. Feige and S. Goldwasser and L. Lovasz and S. Safra and M. Szegedy} ,title= {Approximating Clique is almost {NP}-complete} ,booktitle= {32nd Annual Symposium on Foundations of Computer Science} ,year= 1991 ,pages= {2--3} ,keywords= {graph coloring related theory clique approximation complexity} ) @article( cl: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} ,abstract= {not directly coloring, but related because of finding large independent sets} ) @incollection( cl:fiwi77 ,author= {Stanley Fiorini and Robin J. Wilson} ,title= {Edge-colorings of graphs} ,publisher= {Pitman} ,year= 1977 ,pages= {102--126} ,note= {booktitle?} ,keywords= {graph color} ,series= lnm ,volume= 16 ) @inproceedings( cl:for69 ,author= {J. A. Formby} ,title= {A Computer Procedure for Bounding the Chromatic Number of a Graph} ,booktitle= {Combinatorial Mathematics and its Applications} ,year= 1969 ,editor= {D. J. A. Welsh} ,pages= {111--114} ,publisher= ap ,address= {Proceedings of a Conference in Oxford} ,month= jul ,keywords= {graph coloring algorithms} ) @article( cl: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} ) @inproceedings( cl:fri90a ,author= {Alan M. Frieze} ,title= {Parallel Colouring of Random Graphs} ,booktitle= {Random Graphs '87} ,year= 1990 ,editor= {M. Karo\'{n}ski and J. Jaworski and A. Rudi\'{n}ski} ,pages= {41--52} ,publisher= wiley ,keywords= {graph coloring } ) @article( cl: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} ) @inproceedings( cl:fusu92 ,author= {Martin F\"{u}rer and C. R. Subramanian} ,title= {Coloring Random Graphs} ,booktitle= {The Third Scandinavian Workshop on Algorithm Theory (SWAT '92)} ,year= 1992 ,note= {preprint} ,keywords= {graph coloring random} ) @article( cl:gajo75e ,author= {M. R. Garey and D. S. Johnson} ,title= {On {S}alazar and {O}akford} ,journal= cacm ,year= 1975 ,volume= 18 ,pages= {240-241} ,keywords= {graph coloring} ) @article( cl:gajo76 ,author= {M. R. Garey and D. S. Johnson} ,title= {The complexity of near-optimal graph coloring} ,journal= jacm ,year= 1976 ,volume= 23 ,pages= {43--49} ,keywords= {graph color} ) @article( cl:gaka ,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} ) @article( cl:gav72 ,author= {F\v{a}nic\v{a} Gavril} ,title= {Algorithms for Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of A Chordal Graph} ,journal= sijam ,year= 1972 ,volume= 1 ,number= 2 ,pages= {181--187} ,keywords= {Special graph for coloring, maximum clique ...} ) @article( cl:geli79 ,author= {L. Gerhards and W. Lindenberg} ,title= {Clique detection for nondirected Graphs} ,journal= comp ,volume= 21 ,year= 1979 ,pages= {295--322} ,keywords= {graph coloring related not too good} ) @article( cl: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} ,abstract= { The paper reviews some results and open problems about various nonstandard types of graph coloring. For example, an $L_s$-coloring of a graph $G$ requires that two vertices distance $s$ or less apart (that is, the shortest path joining them has $s$ or fewer edges) be given different colors. This coloring can be extended to directed graphs by requiring different colors of two vertices if they are joined by a directed path of length $s$ or less. Another type of coloring, due to Chartrand, Geller and Hedetniemi, requires that for a given $s$, no path of length $s$ in a graph has all its vertices of the same color. MR} ) @article( cl:gjs76 ,author= {M. R. Garey and D. S. Johnson and I. Stockmeyer} ,title= {Some simplified {NP}-complete graph problems} ,journal= tcs ,year= 1976 ,volume= 1 ,pages= {237--267} ) @article( cl:glo86 ,author= {F. 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( cl: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( cl: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( cl: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} ) @article( cl:gru70 ,author= {B. Gr\"{u}nbaum} ,title= {A Problem in Graph Colouring} ,journal= amm ,year= 1970 ,volume= 77 ,pages= {1088-1092} ,keywords= {graph coloring theory girth false conjecture} ) @techreport( cl:gya85 ,author= {A. 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( cl:gyle88 ,author= {A. Gyarfas and J. 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} ,abstract= {A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called `on-line coloring'. The properties of on-line colorings are investigated in several classes of graphs. In many cases we find on-line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on-line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on-line algorithm: no on-line algorithm can color all trees by a bounded number of colors. MR} ) @article( cl:gyle91 ,author= {Andr\'{a}s Gy\'{a}rf\'{a}s and Jen\"{o} Lehel} ,title= {Online Coloring of $p_5$-Free Graphs} ,journal= comb ,year= 1991 ,volume= 11 ,number= 2 ,pages= {181--184} ,keywords= {graph coloring related algorithms} ) @article( cl: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} ) @incollection( cl: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( cl:hewe87 ,author= { Hertz, A. and de Werra, D.} ,title= { Using tabu search techniques for graph coloring} ,journal= comp ,year= 1987 ,volume= 39 ,number= 4 ,pages= {345--351} ,keywords= {graph color algorithm} ,mrnumbers= { 88m#05038} ,abstract= { The authors explore an iterative heuristics called ``tabu search''. The technique is controlled by a list of forbidden steps which is always updated while going from one feasible solution to another solution. Tabu search is shown by experiments to be computationally superior to simulated annealing for graph $k$-coloring problems.} ) @inproceedings( cl: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} ) @article( cl: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} ) @article( cl: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( cl: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} ) @misc( cl: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( cl: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} ) @inproceedings( cl:ira90 ,author= {Sandy Irani} ,title= {Coloring inductive Graphs On-line} ,booktitle= {31st Annual Symposium on Foundations of Computer Science} ,year= 1990 ,pages= {470--479} ,keywords= {graph coloring related theory} ) @inproceedings( cl:jag92 ,author= {Arun Jagota} ,title= {Efficiently Approximating MAX-CLIQUE in a Hopfield-style Network} ,booktitle= {Proceedings of International Joint Conference on Neural Networks '92 Volume II} ,year= 1992 ,pages= {248--253} ,note= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @article( cl: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} ) @techreport( cl:jare92 ,author= {Arun Jagota and Kenneth W. Regan} ,title= {Performance of MAX-CLIQUE Approximation Heuristics Under Description-Length Weighted Distributions} ,institution= {Department of Computer Science} ,year= 1992 ,address= {State University at New York at Buffalo} ,note= {ftp ftp.cs.buffalo.edu users/jagota or ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @inproceedings( cl:joh74a ,author= {D. 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--528} ,publisher= {Utilitas Mathematica} ,address= {Winnipeg} ,keywords= {graph color} ) @article( cl:joh74b ,author= {D. S. Johnson} ,title= {Approximation Algorithms for Combinatorial Problems} ,journal= jcss ,year= 1974 ,volume= 9 ,pages= {256--278} ,keywords= {graph coloring heuristic algorithms} ) @techreport( cl:joma82 ,author= {A. Johri and D. W. Matula} ,title= {Probabilistic Bounds and Heuristic Algorithms} ,institution= {Southern Methodist University, Department of Computer Science} ,year= 1982 ,type= techrep ,number= {82-CSE-06} ,note= {Supposed to have appeared?} ,keywords= {graph color algorithms} ) @inproceedings( cl: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} ) @article( cl:jyp88 ,author= {D. S. Johnson and M. Yannakakis and C. H. Papadimitriou} ,title= {On generating all maximal independent sets.} ,journal= ipl ,year= 1988 ,volume= 27 ,pages= {119--123} ,keywords= {graph color} ) @inproceedings( cl: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} ,abstract= {max clique is equally hard to approximate as maximum common induced connected subgraph} ) @incollection( cl:kar72 ,author= {R. M. Karp} ,title= {Reducibility among Combinatorial Problems} ,booktitle= {Complexity of Computer Computations} ,publisher= {Plennum Press} ,year= 1972 ,editor= {R. E. Miller and J. W. Thatcher} ,pages= {85--104} ,address= {New York} ,note= {NCPY} ,keywords= {graph coloring complexity} ) @article( cl: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( cl: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} ) @article( cl: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( cl:khu90a ,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} ) @article( cl:khu90b ,author= {Samir Khuller} ,title= {Coloring algorithms for $K_5$-minor free graphs} ,journal= ipl ,year= 1990 ,volume= 34 ,pages= {203--208} ,keywords= {graph color} ) @article( cl:knn82 ,author= {Tsuyoshi Kawaguchi and Hideo Nakano and Yoshiro Nakanishi} ,title= { Probabilistic analysis of a heuristic graph coloring algorithm} ,journal= { Electron. Comm. Japan} ,year= 1982 ,volume= 65 ,number= 6 ,pages= {12--18} ,mrnumbers= {85e#05146} ) @article( cl:koma75 ,author= {R. R. Korfhage and D. W. Matula} ,title= {On {S} and {O}; More on the {S}alazar and {O}akford paper} ,journal= cacm ,year= 1975 ,volume= 18 ,pages= {240,303} ,keywords= {graph coloring} ) @incollection( cl:kor79 ,author= {S. M. Korman} ,title= {the graph-colouring problem} ,booktitle= {Combinatorial Optimization} ,publisher= wiley ,year= 1979 ,editor= {N. Christofides and A. Mingozzi and P. Toth and C. Sandi} ,pages= {211-235} ,keywords= {graph color} ) @article( cl: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( cl:kuc77 ,author= {Lud\u{e}k Ku\u{c}era} ,title= {Expected behavior of graph coloring algorithms} ,booktitle= {FCT '77} ,publisher= sv ,year= 1977 ,pages= {447-451} ,address= {Berlin} ,keywords= {graph color} ,series= lncs ,volume= 56 ) @article( cl:kuc89 ,author= {Lud\u{e}k Ku\u{c}era} ,title= {Graphs with small chromatic numbers are easy to color} ,journal= ipl ,year= 1989 ,volume= 30 ,pages= {233--236} ,keywords= {graph color} ) @incollection( cl:kuc91 ,author= {Lud\u{e}k Ku\u{c}era} ,title= {A Generalized Encryption Scheme Based on Random Graphs} ,booktitle= { 17th Annual Workshop on Graph-Theoretic Concepts in Computer Science {(WG91)} } ,publisher= sv ,year= 1991 ,pages= {180--186} ,address= {Berlin} ,keywords= {hiding independent sets } ,series= lncs ,volume= 570 ) @article( cl: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} ) @inproceedings( cl:kuku83 ,author= {M. Kubale and E. Kusz} ,title= {Computer experiences with implicit enumeration algorithms for graph coloring} ,booktitle= { International workshop on graphtheoretic concepts in computer science. Proceedings of the WG '83} ,year= 1983 ,editor= {M. Nagl and J. Perl} ,pages= {167--176} ,organization= { Universitatsverlag Rudolf Trauner} ,address= { Linz, Austria} ,note= { GCL (ACM Guide to Computing Literature) ACM} ) @article( cl:lawxx ,author= {E. L. Lawler} ,title= {A note on the complexity of the chromatic number problem} ,journal= ipl ,year= {year?} ,volume= 5 ,pages= {66--67} ,note= {full reference} ,keywords= {graph color} ) @article( cl:lei79 ,author= {F. T. Leighton} ,title= {A graph colouring algorithm for large scheduling problems} ,journal= {J. Res. Nat. Bur. Stand.} ,year= 1979 ,volume= 84 ,pages= {489--496} ,keywords= {graph color} ) @article( cl: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( cl: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} ,abstract= {(Max IS can be approximated for planar graphs can be approximated within O(1/(log log OPT)^(1/2)))} ) @article( cl: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} ) @inproceedings( cl:liva89 ,author= {N. Linial and U. Vazirani} ,title= {Graph Products and Chromatic Numbers} ,booktitle= {30th Annual Symposium on Foundations of Computer Science} ,year= 1989 ,pages= {124--128} ,keywords= {graph coloring theory} ) @article( cl: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} ) @article( cl: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= {a algorithm for the independent set of a graph} ) @article( cl: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( cl:lov66 ,author= {L. 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( cl:lov68 ,author= {L. 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( cl:lst89 ,author= {Laszlo L\'{o}vasz 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( cl:luc91a ,author= {Tomasz Luczak} ,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( cl:luc91b ,author= {Tomasz Luczak} ,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} ,abstract= {$\lim_{n \rightarrow \infty} {\rm Prob}\left( u \le \Chi(G(n,p)) \le u +s\right) = 1$ means concentrated in width $s$, $p = p(n)$ for some function $u=u(n)$. Theorem: if $p(n) < n^{-5/6-\epsilon}, \epsilon>0$ then $G(n,p)$ is a.s. two point concentrated. This applies very sparse graphs. } ) @article( cl:mabe83 ,author= {D. W. Matula and L. L. Beck} ,title= { Smallest-last ordering and clustering and graph coloring algorithms} ,journal= jacm ,year= 1983 ,volume= 30 ,number= 3 ,pages= {417--427} ) @inproceedings( cl:maku90 ,author= {David 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. Rucii\'{n}ski} ,pages= {175--187} ,publisher= wiley ,keywords= {graph coloring random graph theory randomization} ) @article( cl:man81 ,author= {B. Manvel} ,title= {Coloring Large Graphs} ,journal= {Proc. 12th Southeastern Conference on combinatorics, Graph Theory and Computing} ,year= 1981 ,pages= {197-204} ) @inproceedings( cl:man85 ,author= {Bennet Manvel} ,title= {Extremely greedy coloring algorithms} ,booktitle= { Graphs and applications (Boulder, Colo., 1982)} ,year= 1985 ,pages= {257--270} ,publisher= wiley ,address= wileya ,series= {Wiley-Intersci. Pub.} ,keywords= {graph color} ,mrnumbers= {86b#05033} ) @article( cl:masa93 ,author= {Carlo Mannino and Antonio Sassano} ,title= {An Exact Algorithm for the Maximum Cardinality Stable Set Problem} ,journal= {Networks} ,year= 1993 ,pages= {(submitted)} ,note= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ) @article( cl:mat68 ,author= {D. 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( cl:mat72 ,author= {D. W. Matula} ,title= {Bounded Color Functions on Graphs} ,journal= {Networks} ,year= 1972 ,volume= 2 ,pages= {29--44} ,note= {NCPY} ,keywords= {graph coloring} ) @article( cl:mat87 ,author= {D. 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} ,abstract= { It is a result of G. Grimmett and C. J. H. McDiarmid [Math. Proc. Cambridge Philos. Soc. 77 (1975), 313--324; MR 51#5365] that, with probability tending to 1 as $n\to \infty$, the chromatic number of the binomial random graph $G(n,p)$, $p$ constant, divided by $\log(1/(1-p))n/\log n$, falls into the interval $(\frac12-\varepsilon,1+\varepsilon)$. For several years the conjecture that the actual value is asymptotically $\frac12$remained unproved. This paper presents an algorithmic approach that results in narrowing the above interval to $(\frac12-\varepsilon, \frac23+\varepsilon)$. This success is due to the introduction of an original way of generating random graphs $G(n,p)$ (called the expose-and-merge exploration), where the order in which pairs of vertices are given the decision edge or nonedge is randomized in a special manner. Some consequences concerning graph coloring algorithms are also given. Reviewer's remarks: B. Bollobas [Combinatorica 8 (1988), no. 1, 49--55] proved the above conjecture using martingales. Very recently T. Luczak combined the expose-and-merge exploration with the Bollobas approach and obtained a similar result for $p=p (n)\to0$, $np>c$, $c$ sufficiently large. } ) @article( cl:mcc83 ,author= {S. T. McCormick} ,title= {Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem} ,journal= matpgm ,year= 1983 ,volume= 26 ,number= 2 ,pages= {153--171} ) @inproceedings( cl: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, San Francisco, Calif.} ,series= {Res. Notes in Math. 34} ,keywords= {graph color} ,mrnumbers= { 82m#05045} ) @article( cl:mcd79b ,author= {C. J. H. McDiarmid} ,title= {Determining the chromatic number of a graph} ,journal= sicomp ,year= 1979 ,volume= 8 ,pages= {1--14} ,keywords= {graph color} ) @article( cl:mcd82 ,author= {Colin McDiarmid} ,title= {Achromatic numers of random graphs} ,journal= mpcps ,year= 1982 ,volume= 92 ,pages= {21--28} ,keywords= {graph color} ) @article( cl: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} ) @article( cl:mcd84 ,author= {Colin McDiarmid} ,title= {Colouring Random Graphs} ,journal= aor ,year= 1984 ,volume= 1 ,pages= {183--200} ,keywords= {graph color} ,abstract= {A survey of random graph coloring} ) @inproceedings( cl:mil75 ,author= {D. M. Miller} ,title= {An algorithm for determining the chromatic number of a graph} ,booktitle= {Proceedings 5th Manitoba Conference on Numerical Math.} ,year= 1975 ,pages= {533} ,keywords= {graph color} ) @article( cl:mit76 ,author= {J. Mitchem} ,title= {On various algorithms for estimating the chromatic number of a graph} ,journal= tcj ,year= 1976 ,volume= 19 ,pages= {182} ,keywords= {graph color} ) @incollection( cl:mmi72 ,author= {David W. Matula and George Marble and Joel D. Isaacson} ,title= {Graph coloring algorithms} ,booktitle= {Graph theory and computing} ,publisher= ap ,year= 1972 ,pages= {109--122} ,keywords= {graph color planar} ,mrnumbers= {50#4368} ) @article( cl: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} ) @article( cl:mosp85 ,author= {B. Monien and E. Speckenmeyer} ,title= {Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem} ,journal= acta ,year= 1985 ,volume= 22 ,pages= {115--123} ,note= {NCPY} ,keywords= {graph coloring} ) @article( cl:muco72 ,author= {G. D. Mulligan and D. G. Corneil} ,title= {Corrections to Bierstone's Algorithm for Generating Cliques} ,journal= jacm ,year= 1972 ,volume= 19 ,number= 2 ,pages= {244--247} ,keywords= {graph coloring related topics} ) @article( cl: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( cl:neta74 ,author= {G. A. Neufeld and J. Tartar} ,title= {Graphs Coloring Conditions for the Existence of Solutions to the Timetable Problem} ,journal= cacm ,year= 1974 ,volume= 17 ,pages= {450--453} ) @article( cl:neta75 ,author= {G. A. Neufeld and J. Tartar} ,title= {Generalized Graph Colorations} ,journal= sijam ,year= 1975 ,volume= 29 ,pages= {91--98} ,keywords= {graph coloring} ) @book( cl:newi90 ,editor= {Roy Nelson and Robin J. Wilson} ,title= {Graph Colourings} ,publisher= {Longman Scientific and Technical} ,year= 1990 ,series= {Pitman Research notes in Mathematics} ,note= {A one day conference: survey papers} ,keywords= {graph color} ) @article( cl: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( cl:ola9x ,author= {S. Olariu} ,title= {All Variations on Perfectly orderable Graphs} ,journal= jctsb ,year= {Unknown} ,note= {to appear} ,keywords= {graph coloring related theory} ) @article( cl:olra89 ,author= {Stephan Olariu and J. Randall} ,title= {Welsh-{P}owell opposition graphs} ,journal= ipl ,year= 1989 ,volume= 31 ,number= 1 ,pages= {43--46} ,keywords= {graph color orderable graphs} ,mrnumbers= { 90f#05118} ) @article( cl:pade91 ,author= {P.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 slightly related} ) @article( cl:paph90 ,author= {P. M. Pardalos and A. 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} ) @article( cl:paro92 ,author= {P.M. Pardalos and G.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--376} ,keywords= {graph coloring related clique} ) @inproceedings( cl: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} ) @article( cl:paxu93 ,author= {Panos M. Pardlos and Jue Xue} ,title= {The Maximum Clique Problem} ,journal= {Journal of Global Optimization} ,year= 1993 ,pages= {(to appear)} ,note= {ftp dimacs.rutgers.edu pub/challenge/graph/contributed} ,annote= {A complete review of the clique problem} ) @inproceedings( cl:paya88 ,author= {Christos H. Papadimitriou and Mihalis Yannakakis} ,title= {Optimization, Approximation and Complexity Classes} ,booktitle= stoc88 ,year= 1988 ,pages= {229--234} ,keywords= {max snp theory } ,abstract= {We define a natural variant of NP, MAX NP, and also a subclass called MAX SNP. These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that problems in these classes can be approximated with some bounded error. Furthermore, we show that a number of common optimization problems are complete under a kind of careful transofrmation (called {\em L-reduction}) that preserves approximability.} ) @article( cl: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} ,keywords= {graph color} ) @article( cl:pee86 ,author= {Peem\"{o}ller, Jurgen} ,title= { Numerical experiences with graph coloring algorithms} ,journal= ejor ,year= 1986 ,volume= 24 ,number= 1 ,pages= {146--151} ,note= {First EURO VI special issue} ,keywords= {graph color} ,mrnumbers= { 87h#0509} ) @techreport( cl:pro91 ,author= {Patrick Prosser} ,title= {Hybrid Algorithms for the Constraint Satisfaction Problem} ,institution= {University of Strathclyde} ,year= 1991 ,type= resrep ,number= {AISL-46-91} ,address= {Dept. of Computer Science, Univ. of Strathclyde, Livingstone Tower, 26 Richmond Street, Glasgow G1 1XH Scotland} ,month= sep ,keywords= {graph coloring related algorithms} ) @article( cl: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} ,note= {Related to Online Graph Coloring} ) @inproceedings( cl:rut86 ,author= {V. Rutenberg} ,title= {Complexity of generalized graph coloring} ,booktitle= { Mathematical foundations of computer science 1986; Proceedings of the twelfth symposium held in Bratislava } ,editor= {J. Gruska and B. Rovan and J. Wiedermann} ,pages= {537--581} ,publisher= sv ,year= 1986 ,volume= 233 ,series= lncs ,month= aug ) @article( cl: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} ) @article( cl:saoa74 ,author= {A. Salazar and R. V. Oakford} ,title= {A Graph Formulation of a School Scheduling Algorithm} ,journal= cacm ,year= 1974 ,volume= 18 ,pages= {241--242} ,note= {see Korfhage and Matula also Garey and Johnson} ,keywords= {graph coloring} ) @article( cl:sco76 ,author= {T. B. Scott} ,title= {Graph Colouring with Preassignment and Unavailability Constraints} ,journal= arsco ,year= 1976 ,volume= 2 ,pages= {25--32} ,keywords= {graph coloring} ) @article( cl:scst80 ,author= {G. Schmidt and T. Str\"{o}hleim} ,title= {Timetable construction --- an annotated bibliography} ,journal= tcj ,year= 1980 ,volume= 23 ,pages= {307} ,keywords= {graph color} ) @article( cl:shsp87 ,author= {E. Shamir and J. Spencer} ,title= {Sharp concentration of the chromatic number of random graphs {$G_{n,p}$}} ,journal= comb ,year= 1987 ,volume= 7 ,pages= {121--129} ,keywords= {graph color} ) @article( cl: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} ) @techreport( cl:shva89 ,author= {S. Shuller and V. V. Vazirani} ,title= {Planar graph coloring is not self-reducible assuming {P} not equal to {NP}} ,institution= {Cornell University, Department of Computer Science} ,year= 1989 ,type= techrep ,number= {89-1064} ,note= {Subfile: STR (Stanford Technical Reports)} ) @inproceedings( cl:sim85 ,author= {Gustavus J. Simmons} ,title= {The {O}chromatic Number of Planar Graphs} ,booktitle= {Graphs and Applications: Proceedigns of the First Colorado Symposium on Graph Theory} ,year= 1985 ,editor= {Frank Harary and John S. Maybee} ,pages= {295--316} ,publisher= wiley ,keywords= {graph coloring related theory} ) @article( cl:sim90 ,author= {Hans-Ulrich Simon} ,title= {On approximate solutions for combinatorial optimization problems} ,journal= siamdm ,year= 1990 ,volume= 3 ,number= 2 ,pages= {294--310} ,keywords= {graph color} ,mrnumbers= {91c#68058} ) @inproceedings ( cl: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) } ,year= 1992 ,pages= { 440-446 } ,address= { San Jose, Calif. } ,keywords= {graph coloring related topics} ) @article( cl:snh76 ,author= {T. Sakaki and K. Nakashima and Y. Hattori} ,title= {Algorithms for finding in lump both bounds of the chromatic number of a graph} ,journal= tcj ,year= 1976 ,volume= 19 ,pages= {329-332} ,keywords= {graph coloring} ) @article( cl:spvi85 ,author= {Jeremy P. Spinrad and Vijayan, Gopalakrishnan} ,title= {Worst case analysis of a graph coloring algorithm} ,journal= dam ,year= 1985 ,volume= 12 ,number= 1 ,pages= {89--92} ,mrnumbers= {86j#05065} ) @article( cl: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( cl:szwi68 ,author= {G. Szekeres and H. S. Wilf} ,title= {An inequality for the chromatic number of a graph} ,journal= jct ,year= 1968 ,volume= 4 ,pages= {1--3} ,keywords= {graph color} ) @article( cl: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( cl:tatr77 ,author= {Robert Endre Tarjan and Anthony E. Trojanowski} ,title= {Finding A Maximum Independent Set} ,journal= sijam ,year= 1977 ,volume= 6 ,number= 3 ,pages= {537--546} ) @article( cl: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} ) @article( cl: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( cl: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( cl:tur67 ,author= {J. 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} ) @techreport( cl:tur85 ,author= {J. S. Turner} ,title= {On the probable performance of graph coloring algorithms} ,institution= {(Washington University, Department of Computer Science} ,year= 1985 ,type= techrep ,number= {WUCS--85--7} ,note= {Subfile: STR (Stanford Technical Reports)} ) @article( cl: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} ) @inproceedings( cl:turn84 ,author= {J. S. Turner} ,title= {On the Probable Performance of Graph Colouring Algorithms} ,booktitle= {Proceedings, 1984 Allerton Conference on Communications, Control and Computing} ,year= 1984 ,pages= {281--290} ,keywords= {graph coloring} ) @incollection( cl:veg84 ,author= {W. Fernandez de la Vega} ,title= {On the chromatic number of sparse random graphs} ,booktitle= {Graph theory and combinatorics, Proceedings {C}ambridge combinatorial conference in hobour of {P}aul {E}rd\"{o}s } ,publisher= ap ,year= 1984 ,editor= {B. Bollob\'{a}s} ,pages= {321--328} ,keywords= {graph color} ) @incollection( cl:veg85 ,author= {W. Fernandex de la Vega} ,title= {Random graphs almost optimally colorable in polynomial time} ,booktitle= {Random Graphs '83} ,publisher= nh ,year= 1985 ,pages= {311-317} ,keywords= {graph color} ,series= adm ,volume= 28 ) @inproceedings( cl: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} ) @inproceedings( cl:vis90 ,author= {S. Vishwanathan} ,title= {Randomized Online Graph Coloring} ,booktitle= {31st Annual Symposium on Foundations of Computer Science} ,year= 1990 ,pages= {464--469} ,keywords= {graph coloring related theory} ) @article( cl: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( cl:wan74 ,author= {C. C. Wang} ,title= {An algorithm for the chromatic number of a graph} ,journal= jacm ,year= 1974 ,volume= 21 ,pages= {385} ,keywords= {graph color} ) @article( cl: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} ) @article( cl:wer74a ,author= {D. de Werra} ,title= {Some Results in Chromatic Scheduling} ,journal= {Z. operations Res. Ser. A} ,year= 1974 ,volume= 16 ,pages= {167--175} ,keywords= {graph coloring} ) @inproceedings( cl:wer74b ,author= {D. de Werra} ,title= {How to Color a Graph} ,booktitle= {Combinatorial Programming --- Methods and Applications} ,year= 1974 ,editor= {B. Roy} ,pages= {305--325} ,organization= nascic ,note= {Vol. 19} ,keywords= {graph coloring} ) @article( cl:wer75 ,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 ,pages= {308--315} ,keywords= {graph coloring timetable} ) @inproceedings( cl:wid82 ,author= {A. Wigderson} ,title= {A New Approximate Graph Coloring Algorithm} ,booktitle= stoc82 ,year= 1982 ,pages= {325--329} ,note= {NCPY} ,keywords= {graph coloring approximation algorithm} ) @article( cl:wig83 ,author= {Avi Wigderson} ,title= { Improving the performance guarantee for approximate graph coloring} ,journal= jacm ,year= 1983 ,volume= 30 ,number= 4 ,pages= {729--735} ) @article( cl:wil67 ,author= {H. 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( cl:wil70 ,author= {M. R. Williams} ,title= {The colouring of very large graphs} ,booktitle= {Combinatorial structures and their applications} ,publisher= {Gordon and Breach} ,year= 1970 ,editor= {R. Guy et al} ,pages= {477--478} ,keywords= {graph color} ) @article( cl: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 ,pages= {119--121} ,keywords= {analysis } ,mrnumbers= { 86c#68036} ) @article( cl: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} ) @article( cl: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} ) @article( cl:woo69 ,author= {D. C. Wood} ,title= {A technique for coloring a graph applicable to large scale timetabling problems} ,journal= tcj ,year= 1969 ,volume= 12 ,pages= {317--319} ,keywords= {graph color} ) @incollection( cl:wowi77 ,author= {D. R. Woodall and Robin J. Wilson} ,title= {The {A}ppel-{H}aken proof of the four color theorem} ,publisher= {Pitman} ,year= 1977 ,pages= {83--101} ,note= {booktitle?} ,keywords= {graph color} ,series= lnm ,volume= 16 ) @booklet( cl: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} ) @inproceedings( cl:you69 ,author= {J. W. T. Youngs} ,title= {Remarks on the Four Color Problem} ,booktitle= {Combinatorial Structures and Their Applications: Proceedings of the Calagary International Conference on Combinatorial Structures and Their Applications} ,year= 1969 ,editor= {Richard Guy and Haim Hanani and Norbert Sauer and Jonathan Schonheim} ,pages= {479--480} ,publisher= {Gordon and Breach} ,keywords= {graph coloring related theory} ) @article( cl:zas82 ,author= {T. Zaslavsky} ,title= {Signed graph coloring} ,journal= dm ,year= 1982 ,volume= 39 ,number= 2 ,pages= {215--228} ) @article( cl:zer89 ,author= {Janez \u{Z}erovnik} ,title= {A randomised heuristical algorithm for estimating the chromatic number of a graph} ,journal= ipl ,year= 1989 ,volume= 33 ,pages= {213--219} ,keywords= {graph color} ) @article( cl:zer90 ,author= {Janez \u{Z}erovnik} ,title= {A parallel variant of a heuristical algorithm for graph coloring} ,journal= parcmp ,year= 1990 ,volume= 13 ,pages= {95--100} ) @article( cl: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( cl:zky52 ,author= {A. A. Zykov} ,title= {On some properties of linear complexes} ,journal= {Mat. Sb.} ,year= 1949 ,volume= 24 ,pages= {163--188} ,note= {English Trans. Amer. Soc. Translation no. 79, 1952} ,keywords= {graph color} )