Responsible: Zsolt Tuza
Prerequisites:
- Algebra and discrete mathematics
- Theory of digital computation
- Combinatorial methods and algorithms
- Linear programming
Areas covered:
- Types of graph coloring, corresponding parameters, basic inequalities, classical upper bounds, constructions;
- Relation to vertex degrees, independence number; chromatic polynomial; compactness principle for infinite graphs;
- Algorithmic complexity of coloring problems, approximability, reductions between different types of coloring;
- Methods applying orientations, algorithms and graph polynomials;
- Some important classes of perfect graphs, Perfekt Graph Theorem, blow-up lemma, characterizations; extendability of colorings in subclasses of perfect graphs;
- Colorings of planar graphs, algorithms; unit-distance colorings of the plane;
- Fractional colorings, multiple colorings, choice ratio.
Literature:
Bodlaender H. L. A tourist guide through treewidth. Acta Cybernetica 11 (1993), 1–21.
Brandstädt A., Le V. B., Spinrad J. P. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, 1999.
Golumbic M. Algorithmic Graph Theory and Perfect Graphs. 2nd ed. Annals of Discrete Mathematics Vol. 57, Elsevier, 2004.
Jensen T. R., Toft B. Graph Coloring Problems. Wiley Interscience, 1995.
Ngo H. Q. Introduction to graph coloring. Online jegyzet: http://www.cse.buffalo.edu/~hungngo/classes/2004/594/notes/Coloring-intro.pdf
Tuza Zs., Graph colorings with local constraints – A survey. Discuss. Math. Graph Theory 17 (1997), 161–228.