Contraction and treewidth lower bounds.
Comparing Imperfection Ratio and Imperfection Index for Graph Classes
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs where the stable set polytope STAB() coincides with the fractional stable set polytope QSTAB(). For all imperfect graphs it holds that STAB() ⊂ QSTAB(). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from...
Frequency planning and ramifications of coloring
This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and...
Page 1