טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentHallufgil Erol
SubjectColoring with Two-Way Independent Sets
DepartmentDepartment of Mathematics
Supervisor Professor Ron Aharoni
Full Thesis textFull thesis text - English Version


Abstract

       The subject of this thesis is two conjectures by Aharoni and Berger on covering by two-way independent sets, namely sets that are independent in both a given graph and a given matroid. We shall prove these conjectures, as well as their dual versions, for matroids of rank 2.

       The first chapter of the thesis is devoted to background and definitions. In chapter 2 we give a proof of a theorem of Haxell on ISRs, and of its corollary, stating that the strong chromatic number of a graph is less than three times of its maximum degree. Chapter 3 and 4 contain the results mentioned above. The matroidal colorability conjecture for matroids of rank 2 is proved in Chapter 3. A conjecture related to chordal graphs is proved in Chapter 4.