Benjamin Leroy-Beaulieu
Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit problem. Chapter 1 presents basic definitions of graph theory, such as graph coloring, graph coloring with color-classes of bounded size b, and Hamiltonian circuits and paths. We also present online algorithms and online coloring. Chapter 2 starts with some general remarks about online graph covering with sets of bounded sizes (such as online bounded coloring): we give a simple method for transforming an online covering algorithm into an online bounded covering algorithm, and to derive the performance ratio of the bounded algorithm from the performance ratio of the unbounded algorithm. As will be shown in later chapters, this method often leads to optimal results. Furthermore, some basic preliminary results on online graph covering with sets of bounded size are given: for every graph, the performance ratio is bounded above by 1/2 + b/2 and for b = 2, this bound is optimal. In the second part, online coloring of co-interval graphs is studied. Based on two industrial applications, two different versions of this problem are discussed. In the case where the intervals are presented in increasing order of their left ends, we show that the performance ratio is 1 in the unbounded case and 2 - 1/b in the bounded case. In the case where the intervals may be presented in any order, we show that the performance ratio is at most 3 in the bounded case. Chapter 3 deals with online coloring of permutation and comparability graphs. First, we give a tight analysis of the First-Fit algorithm on bipartite permutation graphs and we show that its performance ratio is O(√n), even for some simple presentation orders. For both classes of graphs, we show that the performance ratio is bounded above by (χ+1)/2 in the unbounded case and that the performance ratio of First-Fit is equal to 1/2 + b/2 in the bounded case. In the second part of this chapter, we study cocoloring of permutation graphs. We show that the performance ratio is n/4 + 1/2 and we give better bounds in some more restricted cocoloring problems. Chapter 4 deals with an application of online coloring: the online Track Assignment Problem. Depending on the assumptions that are made, the Track Assignment Problem can be reduced to coloring permutation or overlap graphs online. We show that when a permutation graph is presented on a latticial plane, from west to east, then the performance ratio is exactly 2 - (min{b,k})-1, where k is the best known upper bound on the bounded chromatic number. We also show that, when a permutation graph is presented on a latticial plan, starting from the origin and growing, simultaneously or not, towards west and east, then the performance ratio is exactly 2 - 1/χ. We also show that online coloring overlap graphs does not have a performance ratio bounded by a constant, even if the overlap graph is bipartite and presented in increasing order of the intervals left ends. In this special case, we show that First-Fit has a tight performance ratio of O(√n). We consider coloring overlap graphs online where the intervals have a bounded size between 1 and a given number M. In this case, we show that the performance ratio can be bounded above by 2√M if M ≤ M0, and by log M (⎡log M / log log M⎤ + 1) if M > M0, M0 being defined by the equation 2√M0 = 3 log(M0). For large values of M, the ratio is O(log2 M / log log M). Chapter 5 is about online coloring of trees, forests and split-graphs. For trees, we show that the performance ratio of online coloring is exactly ½log2(2n) in the unbouded case and at most 1 + ⎣log2(b)⎦/χb in the bounded case. For split-graphs, we show that the performance ratio of online coloring is exactly 1 + 1/χ in the unbounded case and is at most 2 + 1/χb + 3/b in the bounded case. In Chapter 6, we present a class of digraphs: the quasi-adjoint graphs. These are a super class of both the graphs used for a DNA sequencing algorithm in (Blazewicz, Kasprzak, "Computational complexity of isothermic DNA sequencing by hybridization", 2006) and the adjoints. A polynomial recognition algorithm in O(n3), as well as a polynomial algorithm in O(n2 + m2) for finding a Hamiltonian circuit in quasi-adjoint graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a sequence of two consecutive arcs) are discussed.
EPFL2008
