New algorithmic and hardness results for graph partitioning problems
Marcin Kamiński · Rutgers University Community Repository (Rutgers University) · 2007
In 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 ofP5-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.