This thesis will study a variety of problems in graph theory. Initially, the focus will be on finding minimal degree conditions which guarantee the existence of various subgraphs. These subgraphs will all be formed of cycles, and this area of work will fall broadly into two main categories. First to be considered are cycles in edge-coloured graphs and, in particular, two questions of Li, Nikiforov and Schelp. It will be shown that a 2-edge-coloured graph with minimal degree at least 3n/4 either is isomorphic to the complete 4-partite graph with classes of order n/4, or contains monochromatic cycles of all lengths between 4 and n/2 (rounded up). This answers a conjecture of Li, Nikiforov and Schelp. Attention will then turn to the length of the longest monochromatic cycle in a 2-edge-coloured graph with minimal degree at least cn. In particular, a lower bound for this quantity will be proved which is asymptotically best possible. The next chapter of the thesis then shows that a hamiltonian graph with minimal degree at least (5-sqrt7)n/6 contains a 2-factor with two components. The thesis then concludes with a chapter about X_H, which is the number of copies of a graph H in the random graph G(n,p). In particular, it will be shown that, for a connected graph H, the value of X_H modulo k is approximately uniformly distributed, provided that k is not too large a function of n.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ vertices of the graph. In the same situation, 18 disjoint monochromatic cycles together cover all vertices. Next we show that given any $2$-local edge-colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most $3$ disjoint monochromatic paths. And, we can cover all vertices of any complete or balanced complete bipartite $r$-locally edge-coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path: Every $2$-local edge-colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices. Finally, we prove that any edge-colouring in red and blue of a graph on $n$ vertices and of minimum degree $2n/3 + o(n)$ admits a partition into three monochromatic cycles. This confirms a conjecture of Pokrovskiy approximately. The second part of this thesis contains two independent results about (proper) edge-colouring and parameter estimation respectively. With regards to edge-colouring, we conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. Concerning parameter estimation we study, for any fixed monotone graph property $\mathcal{P}=\text{Forb}(\mathcal{\mathcal{F}})$, the sample complexity of estimating a bounded graph parameter $z_{\mathcal{\mathcal{F}}}$ that, for an input graph $G$, counts the number of {spanning} subgraphs of $G$ that satisfy $\mathcal{P}$. Using a new notion of vertex partitions, we improve upon previous upper bounds on the sample complexity of estimating $z_{\mathcal{\mathcal{F}}}$.

Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.

An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(G)" />. This paper proves an upper bound of the star chromatic index of bipartite graphs in terms of the maximum degree; the maximum degree of G is the largest number of edges incident to a single vertex in G. For bipartite graphs Bk with maximum degree <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?k%5Cgeq1" />, the star chromatic index is proven to satisfy<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%20%5Cchi'_%7Bst%7D(B_k)%20%5Cleq%20k%5E2%20-%20k%20+%201" />. For bipartite graphs <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B_%7Bk,n%7D" />, where all vertices in one part have degree n, and all vertices in the other part have degree k, it is proven that the star chromatic index satisfies <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(Bk,n)%20%5Cleq%20k%5E2%20-2k%20+%20n%20+%201,%20k%20%5Cgeq%20n%20%3E%201" />. We also prove an upper bound for a special case of multipartite graphs, namely <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?K_%7Bn,1,1,%5Cdots,1%7D" /> with m parts of size one. The star chromatic index of such a graph satisfies<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(K_%7Bn,1,1,%5Cdots,1%7D)%20%5Cleq%2015%5Clceil%5Cfrac%7Bn%7D%7B8%7D%5Crceil%5Ccdot%5Clceil%5Cfrac%7Bm%7D%7B8%7D%5Crceil%20+%20%5Cfrac%7B1%7D%7B2%7Dm(m-1),%5C,m%20%5Cgeq%205" />. For complete multipartite graphs where m &lt; 5, we prove lower upper bounds than the one above.

Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.:Mathematics and biology - having nothing in common? I. Going for a start 1. Introducing haplotyping 2. Becoming mathematical II. The MRS problem 3. The graph theoretical point of view 3.1. The MRS problem 3.2. The MRS problem on special graph classes 4. Trying to be not that bad 4.1. Greedy approaches 4.2. The local colour density 4.3. MaxNewColour 5. What is real data telling us? And the work goes on and on Bibliography

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits. / In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs.