@book{GJ, author = "M.~R.~Garey and D.~S.~Johnson", title = "Computers and Intractability", publisher = "W. H. Freeman and Company", year = "1979", address = "New York" } @book{BM, author = {A. Bondy and U.~S.~R. Murty}, title = {Graph Theory with applications}, publisher ={Macmillian}, year = {1976}, address = {London} } @incollection{HandRam, author = {J.~ Ne\v set\v ril}, title = {Ramsey Theory}, booktitle={Handbook of Combinatorics}, publisher ={Elsevier Science}, year = {1995}, editor={R. Graham and M. Gr\"otschel and L. Lov\' asz}, chapter={25} } @article{Brooks, author={R.~L. Brooks}, title={On coloring of nodes of a network}, journal={Proc. Cambridge Phil. Soc.}, volume={37}, year={1941}, pages={194-197} } @article{Ger, author={A. M. H. Gerards}, title={Homomorphisms of graphs into odd cycles}, journal={Jour. Graph Th.}, volume={12}, year={1988}, pages={73-83} } @article{ACG, author={M. O. Albertson and P.A. Catlin and L. Gibbons}, title={Homomorphisms of $3$-chromatic graphs}, journal={Congressus Numerantium}, volume={47}, year={1985}, pages={19-28} } @inproceedings{LO2, author = {L. Lov\'asz}, title = {Problem 2}, booktitle = {Recent advances in graph theory, Proceedings Symposium Prague}, year = {1975}, publisher = {Academia}, address = {Praha} } @article{HH, author={R. H\"aggkvist and P. Hell}, title={Universality of {A}-mote graphs}, journal={Europ. J. Combinatorics}, volume={14}, year={1993}, pages={23-27} } @article{HN1, author={P. Hell and J. Ne{\v s}et{\v r}il}, title={On the complexity of {H}-colouring}, journal={J. Combin. Th. B}, volume={48}, year={1990}, pages={92-100} } @article{HNZ2, author={P. Hell and J. Ne{\v s}et{\v r}il and X. Zhu}, title={Duality and polynomial testing of tree homomorphism}, journal={Trans. Amer. Math. Soc.}, volume={348}, year={1996}, pages={1283-1297} } @article{A, author={G. Ausiello and A. D'Atri and D. Sacc\`a}, title={Minimal representations of directed hypergraphs}, journal={SIAM J. of Computing}, volume={2}, year={1986}, pages={418-431} } @inproceedings{HNZ1, author={P. Hell and J. Ne{\v s}et{\v r}il and X. Zhu}, title={Duality of graph homomorphism}, booktitle = {Combinatorics, Paul Erdos is Eighty(vol.2)}, year = {1996}, publisher = {Bolyai Academy Math. Studies}, pages={271-282} } @article{NP, author={J. Ne{\v s}et{\v r}il and S. Poljak}, title={Complexity of the Subgraph Problem}, journal={Comment. Math. Univ. Carol.}, volume={26.2}, year={1985}, pages={415-420} } @inproceedings{NR, author={J. Ne{\v s}et{\v r}il and V. R{\" o}dl}, title={Type Theory of Partition Properties of Graphs}, booktitle = {Recent advances in graph theory, Proceedings Symposium Prague}, year = {1975}, publisher = {Academia}, address = {Praha}, pages= {405-412} } @inproceedings{FV, author={T. Feder and M. Vardi}, title={Monotone Monadic {SNP} and constraint satisfaction}, booktitle = {Proceedings of the 25th ACM STOC}, year = {1993}, publisher = {ACM} } @article{AlbMoo, author= {M.~Albertson and E.~Moore}, note={Personal Communication} } @inproceedings{Bol, author={B.~Bollob\'as}, title={Extremal graph theory}, booktitle={ Handbook of combinatorics}, volume={2}, year={1995}, publisher={Elsevier, Amsterdam} } @article{BT, author={ B.~Bollob\'as and A.~Thomason}, title={Proof of a conjecture of {M}ader, {E}rd\"os and {H}ajnal on topological complete subgraphs}, journal={Europ. J. Combinatorics}, volume= {19}, year={1998}, pages={883-887} } @article{Bon, author={ J. A. Bondy, and P. Hell}, title={On the star chromatic number}, journal={J. Graph Theory}, volume= {14}, year={1990}, pages={ 479-482} } @inproceedings{Cook, author={R.~J.~Cook}, title={Analogues of {H}eawood's theorem}, booktitle={Combinatorics (Proc. British Combinatorial Conf.), London Math. Soc. Lecture Note Ser., No. 13}, publisher={ Cambridge Univ. Press, London}, year={ 1974}, pages={ 27--33} } @article{Cook1, author={R.~J.~Cook}, title={Chromatic number and girth}, journal={Period. Math. Hungar.}, volume ={6}, year={ 1975}, pages={103--107} } @article{DGM, author= {M.~DeVos and L.~Goddyn and B.~Mohar}, title={Circular chromatic numbers of highly representative graphs on a surface}, note={In preparation} } @article{God, author={ L.~A.~Goddyn and M.~Tarsi and C-Q~Zhang}, title={On $(k,d)$-colorings and fractional nowhere zero flows}, journal={J.~Graph Theory}, volume={28}, year={1998}, pages={155--161} } @article{Gro, author={H.~Gr\"otzsch}, title={Ein Dreifarbensatz f\"ur dreikreisfreie Netze auf der Kugel}, journal={Math. Nat. Reihe}, volume={8}, year={1959}, pages={109--120} } @article{Hol, author={I.~Holyer}, title={The {NP}-completeness of edge-colouring}, journal={SIAM J. Comput.}, volume={10}, year={1981}, pages={718-720} } @article{HZ, author={ P.~Hell and X.~Zhu}, title={The circular chromatic number of series-parallel graphs}, journal={}, volume={}, year={1998}, pages={}, notes={manuscript} } @inproceedings{Jaeger, author={F. Jaeger}, title={Nowhere-zero Flow Problems}, booktitle={Selected Topics in Graph Theory}, volume={3}, publisher={Academic Press}, year={1988}, pages={71-96} } @article{Kosto, author={A. V. Kostochka}, title={Lower bound of the {H}adwiger number of graphs by their average degree}, journal={Combinatorica}, volume={4}, year={1984}, pages={307-316} } @article{KW, author={H.~V.~Kronk and A.~T.~White}, title={A 4-color theorem for toroidal graphs}, journal={Proc. Amer. Math. Soc.}, volume={34}, year={1972}, pages={83-86} } @article{Mader, author={W.~Mader}, title={Homomorphieeigenschaften und mittlere Kantendichte von Graphen}, journal={Math. Ann.}, volume={174}, year= {1967}, pages={265--268} } @article{NesZhu, author={J.~Ne{\v s}et{\v r}il and X.~Zhu}, title={On bounded treewidth duality of graphs}, journal={J.~Graph Theory}, volume={23}, year={1996}, pages={151--162} } @article{RS, author={N. Robertson and P.D. Seymour}, title={Graph Minors. {II}. {A}lgorithmic aspects of treewidth}, journal={J.~Algorithms}, volume={7}, year={1986}, pages={309--322} } @incollection{Sey, author={P. D. Seymour}, title ={Matroid Theory}, booktitle={Handbook of Combinatorics}, volume ={1}, publisher={Elsevier, Amsterdam}, year={1995}, editor={R. Graham and M. Gr\"otschel and L. Lov\' asz}, chapter={10} } @incollection{Sey-HoC, author={P. D. Seymour}, title ={Nowhere-zero flows}, booktitle={Handbook of Combinatorics}, volume ={1}, publisher={Elsevier, Amsterdam}, year={1995}, editor={R. Graham and M. Gr\"otschel and L. Lov\' asz}, note={Appendix to chapter 4} } @incollection{Tho-HoC, author={C. Thomassen}, title ={Embeddings and Minors}, booktitle={Handbook of Combinatorics}, volume ={1}, publisher={Elsevier, Amsterdam}, year={1995}, editor={R. Graham and M. Gr\"otschel and L. Lov\' asz}, chapter={5} } @article{Thom1, author={C.~Thomassen}, title={Gr\"otzsch's theorem and its counterparts for the torus and the projective plane}, journal={ J.~Combin.~Theory Ser.~B}, volume={62}, year={1994}, pages={268-279} } @inproceedings{TH3, author={C.~Thomassen}, title={Paths, Circuits and Subdivisions}, booktitle={Selected Topics in Graph Theory}, volume={3}, publisher={Academic Press}, year={1988}, pages={97-131} } @article{Thomason, author={A.~Thomason}, title={An extremal function for contracting of graphs}, journal={Math. Proc. Cambridge Philos. Soc.}, volume={95}, year={1984}, pages={261-265} } @article{Youngs, author={D. A. Youngs}, title={4-chromatic projective graphs}, journal={J. Graph Theory}, volume={21}, year={1996}, pages={219--227} } @article{Zhang, author={C. Q. Zhang}, title={Circular flows of nearly eulerian graphs and vertex-splitting}, year={1999}, note={Preprint} } @article{Zhou, author={X.~Zhou}, title={Some theorems concerning the star chromatic number of a graph}, journal={ J.~Combin.~Theory Ser.~B}, volume={70}, year={1997}, pages={245--258} } @article{Zhu1, author={X.~Zhu}, title={Star chromatic numbers and products of graphs}, journal={J. Graph Theory}, volume={16}, year={1992}, pages={557--569} } @article{Zhu2, author={X.~Zhu}, title={Planar graphs with circular chromatic numbers between 3 and 4}, journal={}, volume={}, year={}, pages={}, notes={manuscript} } @article{Zhu3, author={X.~Zhu}, title={Circular Chromatic numbers: A survey}, year={1997}, notes={Preprint} }