DescriptionIn this thesis we study algorithmic aspects of two graph partitioning problems -- graph coloring and maximum cut. This is a summary of main results of the thesis:
* A polynomial-time algorithm for k-VERTEX-COLORABILITY in the class of
P5-free graphs (for any fixed value k).
* A proof of NP-completeness of VERTEX- and EDGES_COLORABILITY in the class of graphs with girth at least g for any value of g ≥ 3.
* A polynomial-time algorithm for 3-VERTEX-COLORABILITY of (claw,hourglass)-free graphs and an extension of that result to an infinitely increasing family of subclasses of claw-free graphs.
* An exact algorithm for MAX-CUT running in time O*(2(1-2/Delta)n) in the class of graphs with maximum degree Delta.
* A proof of NP-completeness of MAX-CUT and MAX-BISECTION on unit disk graphs.