Keywords: edge-colored graphs, proper connection, proper hamiltonian paths and cycles, strong edge-colorings, iterated biclique graph

In this thesis, we study different problems in edge-colored graphs and edge-colored multigraphs, such as proper connection, strong edge colorings, and proper hamiltonian paths and cycles. Finally, we improve the known O(n 4 ) algorithm to decide the behavior of a graph under the biclique operator, by studying bicliques in graphs without false-twin vertices. In particular,

• We first study the k-proper-connection number of graphs, this is, the minimum number of colors needed to color the edges of a graph such that between any pair of vertices there exist k internally vertex-disjoint proper paths. We denote this number pc k (G). We prove several upper bounds for pc k (G). We state some conjectures for general and bipartite graphs, and we prove all of them for the case k = 1.

• Then, we study the existence of proper hamiltonian paths and proper hamiltonian cycles in edge-colored multigraphs. We establish sufficient conditions, depending on several parameters such as the number of edges, the rainbow degree, the connectivity, etc.

• Later, we show that the strong chromatic index is linear in the maximum degree for any k-degenerate graph where k is fixed. As a corollary, our result leads to considerable improvement of the constants and also gives an easier and more efficient algorithm for this familly of graphs. Next, we consider outerplanar graphs. We give a formula to find exact strong chromatic index for bipartite outerplanar graphs. We also improve the upper bound for general outerplanar graphs from the 3∆ -3 bound.

• Finally, we study bicliques in graphs without false-twin vertices and then we present an O(n + m) algorithm to recognize convergent and divergent graphs improving the O(n 4 ) known algorithm.

First of all, I would like to thank the reviewers of my thesis, professors Michel Habib et Mickael Montassier, for their useful remarks and comments about my work. Also, I would like to thank the rest of the members of the jury, the examiners of my thesis, professor Dominique Barth and professor Alain Denise for being part of this and for their pertinent questions during the defense. My special thanks to the last member of the jury, professor Marina Groshaus, being her my advisor for my master thesis in Argentina, a great collegue and person. I miss you! Following, to the Laboratoire de Recherche en Informatique for hosting my during these three years of work. Also, for all the collegues that work with me there, Gervais Mendy, Raquel Agueda, Naru, Youg, Sarah, Thomas, etc, etc! For sure, my special thanks goes to Valentin Borozan, a really good friend and partner, now in Budapest. Come back soon Vali!

In the social part, to all my new friends from Paris that were with me making the symptom of being far away from my country much easier. Also to all my friends and family from Argentina that came during these years to visit me and support me. It is always a pleasure to have you here and I hope you will continue to come knowing that you will always be welcome in my place. Among them I thank my parents and brother which spent great time with me here. Also, to my other brother that he did not come so far...(still waiting!) for his support through the distance as the rest of my family and friends in my country that could not come to visit.

I want to thank my mother Cristina, that came alone from Buenos Aires to Paris, specially for my defense and to have christmas here with me. We spent together 20 beautiful days and it was really important to me to have her in this moment of my life. I hope she could come again next year! Te quiero madre!!! To finish, I would like to thank Professor Yannis Manoussakis, my thesis advisor. He was a great guide for me since the beggining, in this new subject of graph theory that I did not work before. He wisely knew how to show me the path for becoming a researcher and I am very grateful for that. He was always available to work in the office (or even as a neighbor!) and always tried to motivate us to obtain the best of us. He was also very helpful with me when I arrived and I did not speak french, helping me to settle down, hire services, being translator, etc. Thank you very much Yannis!! i Résumé Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtescoloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu O(n 4 ) pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément,

• Nous étudions d'abord le nombre k-connexité-propre des graphes, noté pc k (G), ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent k chemins propres intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour pc k (G). Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où k = 1.

• Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc.

• Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe k-dégénéré où, k est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux.

• Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme O(n + m) pour reconnaître les graphes convergents et divergents en améliorant l'algorithme O(n 4 ).

Mots clés: graphes arêtes-coloriés, connexité propre, chaînes et cycles hamiltoniens propres, coloration forte d'arêtes, opérateur biclique.

Chapter 1 Introduction

In this thesis we consider edge-colorings and edge-colored graphs. An edge-coloring of a graph, is an assignment of colors to the edges of the graph. A proper edge-coloring of a graph is an edge-coloring such that adjacent edges have different colors. The natural question is to ask about the minimum number of colors needed in order to color a graph G properly. This number is called chromatic index and denoted by χ (G). By Vizing's Theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF] we know that this number is either ∆(G) or ∆(G) + 1. For several classes of graphs we know exactly the value of χ (G), as for example bipartite graphs which have chromatic index equal to ∆(G). Edge-colorings are interesting not only because of the mathematical point of view, but also because of the many applications they have in real life, for example in scheduling problems and in frequency assignment for fiber optic networks, etc. Therefore, many different types of edge-colorings have been studied over the years. We can cite some of them as strong edge-colorings [START_REF] Andersen | The strong chromatic index of a cubic graph is at most 10[END_REF][START_REF] Brualdi | Incidence and strong edge colorings of graphs[END_REF][START_REF] Chen | A new upper bound of the strong chromatic index[END_REF][START_REF] Cranston | Strong edge-coloring of graphs with maximum degree 4 using 22 colors[END_REF][START_REF] Faudree | Induced matchings in bipartite graphs[END_REF][START_REF] Horák | The strong chromatic index of graphs with maximum degree four[END_REF][START_REF] Horák | Induced matchings in cubic graphs[END_REF][START_REF] Mahdian | The strong chromatic index of C 4 -free graphs[END_REF][START_REF] Molloy | A bound on the strong chromatic index of a graph[END_REF][START_REF] Quinn | Strong chromatic index of subset graphs[END_REF][START_REF] Quinn | Strong chromatic index in subset graphs[END_REF][START_REF] Skupień | Some maximum multigraphs and edge/vertex distance colourings[END_REF][START_REF] Steger | On induced matchings[END_REF][START_REF] Wu | The strong chromatic index of a class of graphs[END_REF], list edge-colorings [START_REF] Borodin | List edge and list total colourings of multigraphs[END_REF][START_REF] Galvin | The list chromatic index of a bipartite multigraph[END_REF][START_REF] Häggkvist | Some upper bounds on the total and list chromatic numbers of multigraphs[END_REF][START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF][START_REF] Lai | Acyclic list edge coloring of graphs[END_REF][START_REF] Lai | Acyclic list edge coloring of planar graphs[END_REF][START_REF] Woodall | List colourings of graphs[END_REF][START_REF] Wu | List-edge and list-total colorings of graphs embedded on hyperbolic surfaces[END_REF][START_REF] Zhang | List edge and list total coloring of 1-planar graphs[END_REF], interval edge-colorings [START_REF] Asratian | Investigation on interval edge-colorings of graphs[END_REF][START_REF] Kamalian | A note on upper bounds for the maximum span in interval edge-colorings of graphs[END_REF][START_REF] Petrosyan | Interval edge-colorings of complete graphs and n-dimensional cubes[END_REF][START_REF] Petrosyan | Interval edge colorings of some products of graphs[END_REF], etc.

An edge-colored graph is a graph that its edges have been colored somehow with c different colors. Here, the natural question to ask is, given an edge-colored graph, how can we find (if possible) or guarantee the existence of some subgraphs with certain properties. For example, how to find or guarantee the existence of a hamiltonian cycle that is properly colored. Lot of research has been done in this subject, not only for proper hamiltonian cycles, but also for proper hamiltonian paths, proper trees, proper cycles, rainbow trees, rainbow paths, rainbow cliques, monochromatic cliques, monochromatic cycles, etc. Refer for example to [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF][START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF][START_REF] Akbari | Multicolored trees in complete graphs[END_REF][START_REF] Alon | Properly colored Hamilton cycles in edge-colored complete graphs[END_REF][START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF][START_REF] Bánkfalvi | Alternating Hamiltonian circuit in two-coloured complete graphs[END_REF][START_REF] Becu | Links in edge-colored graphs[END_REF][START_REF] Benkouar | Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results[END_REF][START_REF] Chou | Paths through fixed vertices in edge-colored graphs[END_REF][START_REF] Feng | Characterization of edge-colored complete graphs with properly colored Hamilton paths[END_REF][START_REF] Hell | Packing problems in edge-colored graphs[END_REF][START_REF] Kano | Monochromatic and heterochromatic subgraphs in edge-colored graphs -a survey[END_REF][START_REF] Manoussakis | Alternating paths in edge-colored complete graphs[END_REF][START_REF] Pevzner | DNA physical mapping and alternating Eulerian cycles in colored graphs[END_REF][START_REF] Pevzner | Computational molecular biology[END_REF][START_REF] Rödl | Rainbow subgraphs in properly edge-colored graphs[END_REF][START_REF] Wang | Color degree and alternating cycles in edge-colored graphs[END_REF][START_REF] Yeo | A note on alternating cycles in edge-coloured graphs[END_REF] to find some results on the subject. This thesis is organized as follows. In chapter two, we give basic definitions and notation. In chapter three, we study the proper connection of graphs. In chapter four, we study strong edge-colorings of graphs, in particular in k-degenerate graphs and outerplanar graphs. In chapter five and chapter six, we study sufficient conditions in edge-colored multigraphs to guarantee the existence of proper hamiltonian paths and cycles, respectively, depending of various parameters such as number of edges, connectivity, rainbow degree, etc. In chapter seven, we present a work that started at the beggining of my PhD thesis when I was in Argentina (with Dr. Marina Groshaus as advisor) and finished here in France. This work is the extension of my master thesis and involves several results in bicliques of graphs, in particular, a linear time algorithm to recognize convergent and divergent graphs under the biclique operator. Finally, in chapter eight, we present the conclusions of our work.

In what follows we present an introduction of the different problems that we have studied in this thesis. The idea is to introduce them by giving some references to the literature such that the reader can find about their history and applications.

Proper connection of graphs

Recent works like [START_REF] Fujita | Properly colored paths and cycles[END_REF][START_REF] Wang | Color degree and alternating cycles in edge-colored graphs[END_REF] have considered properly colored subgraphs as opposed to looking at the entire graph. There is even a survey of work concerning alternating cycles [START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF]. Here alternating means the colors of the edges alternate as you traverse the cycle thus making it properly colored. The problem of finding an alternating cycle is precisely the problem of finding a properly colored cycle when only two colors are available.

Similarly, some researchers have considered rainbow colored subgraphs (meaning that every edge has a distinct color). A graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number, rc(G), as defined in [START_REF] Chartrand | Rainbow connection in graphs[END_REF], is the minimum number of colors that are needed in order to make G rainbow connected. The rainbow connection number was studied in [START_REF] Caro | On rainbow connection[END_REF][START_REF] Chartrand | On the rainbow connectivity of cages[END_REF][START_REF] Dellamonica | Rainbow paths[END_REF][START_REF] Krivelevich | The rainbow connection of a graph is (at most) reciprocal to its minimum degree[END_REF]. Motivated by this, we extend the rainbow connection definition to a proper connection one saying that a graph is k-proper connected if any two vertices are connected by kvertex disjoint paths whose adjacent edges have distinct colors. And define the k-proper connection number, pc k (G), as the minimum number of colors that are needed in order to make G k-proper connected.

About the computational complexity of the problem, there are no results so far. However, there are several results for the rainbow connection problem. We present some of them. Deciding if rc(G) = 2 or rc(G) = k, for any fixed k ≥ 2, is N P -Complete [START_REF] Chakraborty | Hardness and algorithms for rainbow connectivity[END_REF] and [START_REF] Le | Finding optimal rainbow connection is hard[END_REF] respectively. Checking whether the given coloring makes G rainbow connected is N P -complete [START_REF] Chakraborty | Hardness and algorithms for rainbow connectivity[END_REF]. But, the problem is polynomial for complete graphs, trees, paths, cycles and wheels [START_REF] Chartrand | Rainbow connection in graphs[END_REF].

In this thesis we first study pc k (G) for bipartite graphs. We prove exact values of pc k (G) for different bipartite complete graphs and trees. Then, we state the general conjecture that says that if G is 2k-connected and bipartite with k ≥ 1, then pc k (G) = 2. We prove that, if true, the conjecture is the best possible since we show a family of 2k -1-connected bipartite graphs with pc k (G) > 2. Finally, we prove this conjecture for k = 1.

Later, we study pc k (G) in general graphs, starting with the simplest case k = 1, i.e., pc(G). We prove several exact values for pc(G) as for example for complete graphs, paths, cycles, etc. Then, we prove the main result of the section, this is, if G is 2-connected, then pc(G) ≤ 3. This improves Vizing's trivial bound of ∆ + 1. We show also that this bound is tight since we present a family of 2-connected graphs with pc(G) = 3. Then we present a bound for pc(G) for just connected graphs that uses the maximum degree of a vertex that is an endpoint of a bridge. We state also a general conjecture for pc k (G) based on the conjecture for bipartite graphs and the result for 2-connected graphs. This is, if G is 2k-connected with k ≥ 1, then pc k (G) ≤ 3. We remark that we proved this conjecture for k = 1. Then, we prove a stronger result for pc k (G) for complete graphs of order n ≥ 2k.

Finally, we prove a result concerning the minimum degree of the graph, this is, if G is a connected non-complete graph of order n ≥ 68 and δ(G) ≥ n 4 then pc(G) = 2. All our results lead to efficient algorithms to find such colorings. We remark that many of the conditions assumed for proper connection are much weaker than those needed to produce upper bounds on the rainbow connection number rc(G). This can be explained by the fact that it takes far fewer colors to make a path properly colored than are needed to make it rainbow colored.

Strong edge-colorings

A strong edge-coloring of a graph G is an edge-coloring such that any two vertices belonging to distinct edges with the same color are not adjacent. The strong chromatic index, χ s (G), is the minimum number of colors in a strong edge-coloring of G.

The strong edge-coloring has a long history and has lead to many well known conjectures. Some of the many unsolved conjectures include χ s (G) ≤ 5∆ 2 /4 for all graphs, χ s (G) ≤ ∆ 2 for bipartite graphs, and χ s (G) ≤ 9 for 3-regular planar graphs (see the open problems pages of Douglas West [START_REF] West | Open problems -graph theory and combinatorics[END_REF] for more details).

Molloy and Reed [START_REF] Molloy | A bound on the strong chromatic index of a graph[END_REF] proved a conjecture by Erdős and Nešetřil (see [START_REF] Faudree | Induced matchings in bipartite graphs[END_REF]) that for large ∆, there is a positive constant c such that χ s (G) ≤ (2c)∆ 2 . Mahdian [START_REF] Mahdian | The strong chromatic index of C 4 -free graphs[END_REF] proved that for a C 4 -free graph G, χ s (G) ≤ (2 + o(1))∆ 2 / ln ∆.

For integers 0 ≤ ≤ k ≤ m, S m (k, ) is the bipartite graph with vertex set {x ⊆ [m] : |x| = k or } and a k-subset x is adjacent to an -subset y if y ⊆ x. Quinn and Benjamin [START_REF] Benjamin | Strong chromatic index of subset graphs[END_REF] proved that S m (k, ) has strong chromatic index m k-. The Θ-graph Θ(G) of a partial cube G (distance-invariant subgraph of some n-cube), is the intersection graph of the equivalence classes of the Djoković-Winkler relation Θ defined on the edges of G such that xy and uv are in relation Θ if d(x, u) + d(y, v) = d(x, v) + d(y, u). Šumenjak [START_REF] Šumenjak | Θ-graphs of partial cubes and strong edge colorings[END_REF] showed that the strong chromatic index of a tree-like partial cube graph G is at most the chromatic number of Θ(G).

Faudree, Gyárfás, Schelp and Tuza [START_REF] Faudree | The strong chromatic index of graphs[END_REF] proved that for graphs where all cycle lengths are multiples of four, χ s (G) ≤ ∆ 2 . They mention that this result probably could be improved to a linear function of the maximum degree. Brualdi and Quinn [START_REF] Brualdi | Incidence and strong edge colorings of graphs[END_REF] improved the upper bound to χ s (G) ≤ αβ for such graphs, where α and β are the maximum degrees of the respective partitions. Nakprasit [START_REF] Nakprasit | A note on the strong chromatic index of bipartite graphs[END_REF] proved that if G is bipartite and the maximum degree of one partite set is at most 2, then χ s (G) ≤ 2∆. Bounds for outerplanar graphs were given recently in [START_REF] Hocquard | Strong edge coloring and induced matching[END_REF]. A recent work ( [START_REF] Kloks | Algorithms for the strong chromatic index of halin graphs, distance hereditary graphs and maximal outerplanar graphs[END_REF]) gives an algorithm to find the strong chromatic index of any maximal outerplanar graph, but notice that when you extend the graph to maximal outerplanar, the maximum degree and the chromatic index can increase. Also, Chang and Narayanan [START_REF] Chang | Strong chromatic index of 2-degenerate graphs[END_REF] proved that χ s (G) ≤ 10∆-10 for any 2-degenerate graph G, χ s (G) ≤ 8∆ -6 for chordless graphs and proposed, as a conjecture, that there exists an absolute constant c such that for any k-degenerate graph G, χ s (G) ≤ ck 2 ∆. Thus for fixed k, χ s (G) is linear in ∆.

About the complexity, the strong edge-coloring problem is N P -complete [START_REF] Mahdian | On the computational complexity of strong edge coloring[END_REF]. It is also N P -complete for 4, 5 or 6 colors in some subclasses of planar graphs of maximum degree 3 [START_REF] Hocquard | Strong edge coloring and induced matching[END_REF]. However, is polynomial for some classes of graphs as paths, trees, cycles, chordal graphs [START_REF] Cameron | Induced matchings[END_REF], graphs of bounded tree-width [START_REF] Salavatipour | A polynomial time algorithm for strong edge coloring of partial k-trees[END_REF], etc.

One known application of strong edge-colorings is the following: to find a minimum strong edge-coloring (χ s (G)) is equivalent to computing an interference-free channel assignment with the fewest channels [START_REF] Barrett | Strong edge coloring for channel assignment in wireless radio networks[END_REF].

In this thesis, we will be focused in improving bounds for k-degenerate graphs and outerplanar graphs. In particular, we prove that if G is k-degenerate graph, then χ s (G) ≤ (4k -1)∆ -2k 2k + 1 that improves the conjecture since χ s (G) is linear in ∆ and k.

This result implies the two following ones. If G is 2-degenerate graph, then χ s (G) ≤ 7∆ -9 and if G is chordless, then χ s (G) ≤ 5∆ -5, improving both known results. Then we show an O(n + k∆m) algorithm to find a coloring for k-degenerate graphs using (4k -1)∆ -2k 2k + 1 colors.

Then, for strong edge-colorings in outerplanar graphs, we define a puffer graph or an npuffer as a graph obtained by adding some (possibly empty) pendant edges to each vertex of an n-cycle or adding a common neighbour to two consecutive vertices of the n-cycle. We remark that since the graph is outerplanar, at most one such vertex can be added. We prove several exact and upper bounds for χ s (G) in puffer graphs. Using these results we prove the following: if G is an outerplanar graph, then χ s (G) = max{max uv∈E d(u) + d(v) -1, max H∈P χ s (H)}, where P is the set of all induced puffer subgraphs of G. If G is also bipartite, then χ s (G) = max{max uv∈E d(u) + d(v) -1, max uv∈E(C 4 ) d(u) + d(v)} where C 4 is the set of all cycles of length 4 in G. Observe that for outerplanar graphs we obtain an upper bound for χ s (G), while for bipartite outerplanar graphs we have the exact value of χ s (G).

Proper hamiltonian paths and cycles in edgecolored multigraphs

The research on long colored cycles and paths for edge-colored graphs has given interesting results. Refer to [START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF][START_REF] Bang-Jensen | Digraphs[END_REF][START_REF] Kano | Monochromatic and heterochromatic subgraphs in edge-colored graphs -a survey[END_REF] for surveys on related results. From the point of view of applicability, problems arising in molecular biology are often modeled using colored graphs, i.e., graphs with colored edges and/or vertices [START_REF] Pevzner | Computational molecular biology[END_REF]. Given such an edge-colored graph, original problems translate to extracting subgraphs colored in a specified pattern. The most natural pattern in such a context is that of a proper coloring, i.e., adjacent edges have different colors.

Clearly, the proper hamiltonian path and proper hamiltonian cycle problems are N Pcomplete in the general case. It is polynomial to find a proper hamiltonian path in c-edgecolored complete graphs, c ≥ 2 [START_REF] Feng | Characterization of edge-colored complete graphs with properly colored Hamilton paths[END_REF]. It is also polynomial to find a proper hamiltonian cycle in 2-edge-colored complete graphs [START_REF] Bánkfalvi | Alternating Hamiltonian circuit in two-coloured complete graphs[END_REF]. It is still open to determine the computational complexity for proper hamiltonian cycles, c ≥ 3 [START_REF] Benkouar | Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results[END_REF]. Many other partial results for edge-colored multigraphs can be found in the survey by Bang-Jensen and Gutin [START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF].

In this thesis we consider sufficient conditions involving various parameters as the number of edges, rainbow degree, etc., in order to guarantee the existence of properly edge-colored hamiltonian paths and cycles in edge-colored multigraphs. Since, very often the extremal graphs for 2-edge-colored multigraphs are different than those for c-edgecolored multigraphs, c ≥ 3, we consider our results separately for these two cases. This division is natural since in 2-edge-colored multigraphs proper paths and proper cycles are just alternating, and therefore, the bounds are different.

For proper hamiltonian paths in 2-edge-colored multigraphs we present two main results. The first one involves the number of edges, and the second one involves the number of edges and the rainbow degree. We show that both results are tight. Then, for proper hamiltonian paths in c-edge-colored multigraphs, c ≥ 3, we show that this problem can be reduced to the existence of proper hamiltonian paths in 3-edge-colored multigraphs and then we present three main results. The first one involves the number of edges. The second one, the number of edges and the connectivity of the graph. The last one, the number of edges and the rainbow degree. Again, all results are the best possible.

About proper hamiltonian cycles in 2-edge-colored multigraphs we prove two tight results involving same parameters as for proper hamiltonian paths. Then, for c-edge-colored multigraphs, c ≥ 3, we show, as for paths, that looking at 3-edge-colored multigraphs is enough and then we prove two main results. The first one involves the number of edges. The second one, the number of edges and the rainbow degree. We show that both results are the best possible. Finally, we state a conjecture involving the number of edges, the rainbow degree and the 2-connectivity of the graph.

Results involving only degree conditions can be found in [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF].

Bicliques in graphs

Intersection graphs of certain special subgraphs of a general graph have been studied extensively. Let us mention for example the case of line graphs (which are the intersection graphs of the edges of a graph), interval graphs (defined as the intersection graphs of intervals of the real line), and, in particular, clique graphs (defined below) [START_REF] Booth | Testing for the consecutive ones property, interval graphs, and graph planarity using P Q-tree algorithms[END_REF][START_REF] Brandstädt | Graph Classes: a Survey[END_REF][START_REF] Escalante | Über iterierte Clique-Graphen[END_REF][START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF][START_REF] Gavril | The intersection graphs of subtrees in trees are exactly the chordal graphs[END_REF][START_REF] Lehot | An optimal algorithm to detect a line graph and output its root graph[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF].

The clique graph of G, denoted by K(G), is the intersection graph of the family of all maximal cliques of G.

Clique graphs were introduced by Hamelink in [START_REF] Hamelink | A partial characterization of clique graphs[END_REF] and characterized by Roberts and Spencer in [START_REF] Roberts | A characterization of clique graphs[END_REF]. It was proved in [START_REF] Alcón | Clique graph recognition is NP-complete[END_REF] that the clique graph recognition problem is NPcomplete.

As the clique graph construct can be thought of as an operator between graphs, the iterated clique graph K k (G) is the graph obtained by applying the clique operator k successive times. It was introduced by Hedetniemi and Slater in [START_REF] Hedetniemi | Line graphs of triangleless graphs and iterated clique graphs[END_REF]. Much work has been done on the scope of the clique operator, looking at the different possible behaviors.

The associated problem is deciding whether an input graph converges, diverges, or is periodic under the clique operator, when k grows to infinity. In general, it is not clear that the problem is decidable. However, partial characterizations have been given for convergent, divergent and periodic graphs, restricted to some classes of graphs. Some of these lead to polynomial time recognition algorithms. For the clique-Helly graph class, graphs which converge to the trivial graph have been characterized in [START_REF] Bandelt | Clique graphs and Helly graphs[END_REF]. Cographs, P 4tidy graphs, and circular-arc graphs are examples of classes where the different behaviors are characterized [START_REF] De Mello | The clique operator on graphs with few P 4 's[END_REF][START_REF] Larrión | The clique operator on cographs and serial graphs[END_REF]. Divergent graphs were also considered. For example, in [START_REF] Lara | Clique divergence in graphs[END_REF], families of divergent graphs are shown. Periodic graphs were studied in [START_REF] Escalante | Über iterierte Clique-Graphen[END_REF][START_REF] Larrión | Whitney triangulations, local girth and iterated clique graphs[END_REF]. In particular, it is proved that for every integer i, there exist graphs with period i and convergent graphs which converge in i steps. More results about iterated clique graph can be found in [START_REF] Pizaña | Equivariant collapses and the homotopy type of iterated clique graphs[END_REF][START_REF] Frías-Armenta | Dismantlings and iterated clique graphs[END_REF][START_REF] Larrión | A family of clique divergent graphs with linear growth[END_REF][START_REF] Larrión | Clique divergent graphs with unbounded sequence of diameters[END_REF][START_REF] Larrión | Locally C 6 graphs are clique divergent[END_REF][START_REF] Pizaña | The icosahedron is clique divergent[END_REF].

The biclique graph of a graph G, denoted by KB(G), is the intersection graph of the family of all maximal bicliques of G. It was defined and characterized in [START_REF] Groshaus | Biclique graphs and biclique matrices[END_REF]. However, no polynomial time algorithm is known for recognizing biclique graphs. As for clique graphs, the biclique graph construct can be viewed as an operator KB between graphs.

The iterated biclique graph KB k (G), i.e., the graph obtained by applying iteratively the biclique operator KB k times to G was introduced and all possible behaviors were characterized in [START_REF] Groshaus | On the iterated biclique operator[END_REF]. It was proven that a graph G is either divergent or convergent, but it is never periodic (with period bigger than 1). In addition, they were given general characterizations for convergent and divergent graphs. These results are based on the fact that if a graph G contains a clique of size at least 5, then KB(G) contains a clique of larger size. Therefore, G diverges. Similarly, if G contains the so-called gem or rocket as an induced subgraph, then KB(G) contains a clique of size 5, and again, G diverges. Otherwise, it is shown that, after removing false-twin vertices of KB(G), the resulting graph is a clique on at most 4 vertices, in which case, G converges. Moreover, it was proved that if a graph G converges, it converges to the graphs K 1 or K 3 , and it does so in at most 3 steps. These results are very different from the ones known for the clique operator. These characterizations leaded to an O(n 4 ) time algorithm for deciding if a given graph converges or diverges under the biclique operator.

Bicliques have applications in various fields, for example, biology: protein-protein interaction networks [START_REF] Bu | Topological structure analysis of the proteinprotein interaction network in budding yeast[END_REF], social networks: web community discovery [START_REF] Kumar | Trawling the web for emerging cyber-communities[END_REF], genetics [START_REF] Atluri | Discovering coherent value bicliques in genetic interaction data[END_REF], medicine [START_REF] Nagarajan | Uncovering genomic reassortments among influenza strains by enumerating maximal bicliques[END_REF], information theory [START_REF] Haemers | Bicliques and eigenvalues[END_REF]. More applications (including some of these) can be found in [START_REF] Liu | Efficient mining of large maximal bicliques[END_REF] In this thesis we continue this work. Using the characterization above and other results we prove that if G has at least 7 bicliques, then G diverges under the biclique operator, i.e., almost every graph is divergent under the biclique operator. Later, based on those results we obtain the main theorem that leads to a linear time algorithm for deciding if a given graph converges or diverges under the biclique operator. Motivated by the fact that false-twin vertices belong to exactly the same bicliques and the successive deletion of them does not change neither the number of bicliques of the graph nor the structure of the biclique graph (and therefore does not change its behavior under the biclique operator), we study this particular class. We prove that given a graph G with no false-twin vertices, if G has at least 13 vertices then G has at least 7 bicliques. Later, we study more general structural properties of bicliques in false-twin free graphs. We prove several small results that imply the following: If G is a K 3 -free graph of order n ≥ 4 without false-twin vertices, then G has at least n 2 bicliques. We also state a similiar conjecture but for general graphs without false-twin vertices. Finally, we present several results that would help to prove that conjecture.

Chapter 2

Definitions and Notation

In this chapter we introduce the main definitions and notation needed to understand this thesis. We begin by the general notions of graph theory, then about edge-colored graphs and multigraphs, and finally about bicliques in graphs. We use the notation and terminology given by Bondy and Murty in [START_REF] Bondy | Graph theory with applications[END_REF]. However, the reader is warned that there may be some differences.

General graphs

A graph is an ordered pair G = (V (G), E(G)), where V (G) is a non-empty finite set and E(G) is a set of unordered pairs vw with v, w ∈ V (G) and v = w. The set V (G) or simply V , is the vertex set of G and its elements are called vertices of G. The set E(G) or simply E is the edge set of G and its elements are called edges of G. Given an edge e = vw, the vertices v and w are called endpoints of e. The order of G is the number of vertices of G. We denote, as usual, n = |V (G)| and m = |E(G)|, unless otherwise stated. The unique graph of order 1 is called the trivial graph. We remark that in our graph

definition vv / ∈ E(G) for v ∈ V (G), vw ∈ E(G) if and only if wv ∈ E(G) for v, w ∈ V (G) and |{vw ∈ E(G)|v, w ∈ V (G)}| ≤ 1.
Under these conditions we refer to these graphs as loopless, undirected and simple respectively. A vertex v is adjacent to a vertex w when vw ∈ E(G). We also say in that case that v is a neighbor of w. A vertex v is incident to an edge e when v is an endpoint of e. Two distinct edges e and f are adjacent if they have a common endpoint. The neighborhood of a vertex v, denoted N G (v), is the set of all neighbors of v, and the complement neighborhood of a vertex v, denoted N G (v), is the set of all non-neighbors of v. The degree of a vertex v is the cardinality of the set N G (v) and it is denoted d G (v). The minimun and maximum values among the degrees of all vertices are denoted δ(G) and

∆(G) respectively. If δ(G) = ∆(G) then G is a regular graph. The closed neighborhood of v is the set N G [v] = N G (v) ∪ {v}. If N G [v] = V (G) then v is an universal vertex while if N G (v) = ∅
then v is an isolated vertex. We will omit the subscripts in N and d when there is no ambiguity about G. Two vertices v and w are true-twins, or simply twins, when N [v] = N [w]. We refer to v and w as false-twins when

N (v) = N (w). A graph H is a subgraph of the graph G if V (H) ⊆ V (G) and E(H) ⊆ E(G). If also E(H) = {vw ∈ E(G)|v, w ∈ V (H)}, then H is an induced subgraph of G. For each S ⊆ V (G), the subgraph of G induced by S is the unique induced subgraph of G whose vertex set is S. We denote by G[S] the subgraph of G induced by V . A subgraph of G whose vertex set is V (G) is called a spanning subgraph. For each S ⊆ V (G), we denote by G -S the subgraph of G induced by V (G) -S. If S = {v}, we write shortly G -v.
Similarly, for each F ⊆ E(G), we denote by G -F the spanning subgraph of G with edge set E(G) -F . If F = {e}, we write shortly Ge. A graph is k-degenerate, if every subgraph has a vertex of degree at most k.

Two graphs G and H are isomorphic if there is a one-to-one mapping f between V (G) and V (H) such that vw ∈ E(G) if and only if f (v)f (w) ∈ E(H). The mapping f is referred to as an isomorphism between G and H. For a graph H, the graph

G is H -f ree if no induced subgraph of G is isomorphic to H.
The complement of a graph G, denoted by G, is the graph that has the same vertices as G and such that two vertices are adjacent in G if and only if they are not adjacent in G.

A walk in a graph G is a sequence v 1 . . . v k of vertices such that v i is adjacent to v i+1 , for every 1 ≤ i < k. Such a walk is said to be a walk between v 1 and v k (or joining v 1 with v k ). The vertices v i and v i+1 are said to be consecutive in the walk and v i v i+1 is said to be an edge of the walk. The length of the walk is the number k -1 of edges of the walk. A closed walk is a walk that joins a vertex with itself. A path is a walk formed by pairwise distinct vertices and it is denoted by

P k . A cycle is a closed walk v 1 . . . v k v 1
where k ≥ 3 and v 1 . . . v k is a path. We denote it by C k . A hamiltonian path (cycle) is a path (cycle) containing all vertices of the graph.

A graph is connected if it contains a path between any two of its vertices. A disconnected graph is a graph that is not connected. A connected component, or simply a component, is a maximal connected subgraph. A graph is k-connected if for any set S of k -1 vertices, G -S is connected. The connection number of a graph is the minimum value k that there exists a set of vertices S of size k such that G -S is disconnected and for every set of vertices S of size k -1, G -S remains connected. We denote it by κ(G). Similarly, A graph is k-edge-connected if for any set

F of k -1 edges, G -F is connected. A vertex v of a connected graph G such that G -v is disconnected is called cut vertex, similarly a set of vertices S of a connected graph G such that G -S is disconnected is called cut set. A edge e of a connected graph G such that G -e is disconnected is called bridge.
A forest is a graph without cycles. A tree is a connected graph without cycles. A leaf of a tree is a vertex of degree 1.

The distance of two vertices v and w in a graph G, denoted by d G (v, w), is the minimum among the lengths of all the paths between v and w. The distance of v and w is infinity when there is no path joining v with w. The max u,v∈V d(u, v) is called the diameter of G.

A chord of a cycle is an edge that joins two non-consecutive vertices of the cycle. Those cycles that have no chords are called chordless. A graph is chordless if every cycle is chordless.

A clique in a graph G is a set of pairwise adjacent vertices. An independent set is a set of pairwise non-adjacent vertices. The complete graph of order n is denoted by K n and K 3 is referred to as a triangle.

A graph G is bipartite when there is a partition of V (G) into two non-empty sets

V 1 , V 2 of V (G) such that both V 1 and V 2 are independent sets. The partition V 1 , V 2 is called a bipartition of V (G), and we denote it by V 1 , V 2 . If each vertex in V 1 is adjacent to all the vertices in V 2 , then G is a complete bipartite graph. The complete bipartite graph with bipartition V 1, V 2 is denoted by K |V 1|,|V 2| .
A matching in a graph is a set of pairwise non-adjacent edges. Given a graph of order n, for n even, a perfect matching is a matching M of G such that |M | = n 2 and for n odd, an almost perfect matching is a matching M of G such that |M | = n-1 2 . A path or cycle is said to be compatible with a matching M if the edges of the path or the cycle are alternatively in M and not in M . We assume that, if the path is not hamiltonian, it starts and ends with edges in

M . An induced matching M in G is a matching such that G[V (M )] = M . That is, the subgraph of G induced by the vertices of M is M itself.
A graph G is outerplanar, if it has a planar embedding in which all vertices are incident to the infinite face. We define a special outerplanar graph and we call it puffer graph or an n-puffer as a graph obtained by adding some (possibly empty) pendant edges to each vertex of an n-cycle or adding a common neighbour to two consecutive vertices of the ncycle. Notice that since the graph is outerplanar, at most one such vertex can be added.

Depending on whether the parity of the cycle is even or odd, they are respectively called even puffer and odd puffer.

Edge-colored graphs

Let C = {1, 2, • • • , c} be a set of c ≥ 2 colors. A c-edge-coloring of a graph G is a mapping between C and E(G) such that each of the c colors if assigned to at least one edge of G. A proper c-edge-coloring is a c-edge-coloring such that every pair of adjacent edges have different colors. The smallest positive integer c such that G admits a proper c-edge-coloring is known as the chromatic index of G and is denoted χ (G). A color class (in an edge-coloring) is the set of all edges which receive the same color.

If H is a subgraph of G, then N i H (v) denotes the set of vertices of H adjacent to v with an edge of color i. Whenever H is isomorphic to G, we write N i (x) instead of N i G (v). The colored i-degree of a vertex v, denoted by d i (v), is the cardinality of N i (v). The rainbow degree of a vertex v, denoted by rd(v), is the number of different colors on the edges incident to v. The rainbow degree of a graph, denoted by rd(G), is the minimum rainbow degree among all vertices of G. An edge with endpoints v and w is denoted by vw, and its color by c(vw). A vertex is monochromatic if it has all its incident edges of the same color.

A path or cycle in an edge-colored graph is said to be properly edge-colored (or proper ), if every two adjacent edges differ in color. A proper hamiltonian path (cycle) is a proper path (cycle) containing all vertices of the graph. An edge-colored graph G is k-proper connected if any two vertices are connected by k internally pairwise vertex-disjoint proper paths. We define the k-proper connection number of a k-connected graph G, denoted by pc k (G), as the smallest number of colors that are needed in order to make G k-proper connected. Similarly, An edge-colored graph G is k-proper edge-connected if any two vertices are connected by k internally pairwise edge-disjoint proper paths. We define the k-proper edge-connection number of a k-edge-connected graph G, denoted by pec k (G), as the smallest number of colors that are needed in order to make G k-proper edge-connected. An edge-colored graph is connected if the underlying non-colored graph is connected.

Given a colored path P = v 1 v 2 . . . v s-1 v s between any two vertices v 1 , v s , we denote by start(P ) the color of the first edge in the path, i.e. c(v 1 v 2 ), and by end(P ) the last color, i.e. c(v s-1 v s ). If P is just the edge v 1 v s then start(P ) = end(P ) = c(v 1 v s ).

A proper edge-coloring is a strong edge-coloring, if every color class is an induced matching in G. In other words, the distance between any two edges having the same color is at least two. The minimum positive integer k such that G admits a strong k-edgecoloring is called the strong chromatic index of G denoted χ s (G).

Edge-colored multigraphs

A multigraph is a loopless, undirected graph, i.e., the condition of being simple is dropped (several edges between the same pair of vertices are allowed). Let C = {1, 2, • • • , c} be a set of c ≥ 2 colors. A c-edge-coloring of a multigraph is an edge-coloring such that every edge is colored with one color and no two parallel edges joining the same pair of vertices have the same color. We denoted it by G c .

A rainbow complete multigraph is the one having all possible colored edges between any pair of vertices.

We use two families of multigraphs without proper hamiltonian paths. First, let

H 2 k,k+3
denote a 2-edge-colored multigraph on 2k + 3 vertices, k ≥ 1, defined as follows. Consider a complete red graph on k vertices and join it with red edges to an independent set on k + 3 vertices. Finally, superpose a complete blue graph on 2k + 3 vertices. For the second family, let H c k,k+2 denote a c-edge-colored multigraph on 2k + 2 vertices, k ≥ 1 and c ≥ 3. Consider a rainbow complete graph on k vertices and join it with edges of all possible colors to an independent set on k + 2 vertices.

Finally we use two families of multigraphs without proper hamiltonian cycles. Let H 2 k,k+2 denote a 2-edge-colored multigraph on 2k + 2 vertices, k ≥ 2. Consider a complete red graph on k vertices and join it with red edges to an independent set on k + 2 vertices. Finally, superpose a complete blue graph on 2k + 2 vertices. Let H c k,k+1 denote a c-edgecolored multigraph on 2k + 1 vertices, k ≥ 2 and c ≥ 3. Consider a rainbow complete graph on k vertices and join it with edges of all possible colors to an independent set on k + 1 vertices.

Bicliques in graphs

A biclique is a maximal complete bipartite induced subgraph of G. A diamond is a complete graph with 4 vertices minus an edge. A gem is an induced path with 4 vertices plus an universal vertex. A rocket is a complete graph with 4 vertices and a vertex adjacent to two of them.

Given a family of sets A, the intersection graph of A has as vertices the set of A and the edges correspond to the pairs of sets from A with a non-empty intersection. We remark that any graph is an intersection graph [START_REF] Szpilrajn-Marczewski | Sur deux propriétés des classes d'ensembles[END_REF].

The clique graph of G, denoted by K(G), is the intersection graph of the family of all maximal cliques of G. The biclique graph of a graph G, denoted by KB(G), is the intersection graph of the family of all maximal bicliques of G.

Let F be any graph operator. Given a graph G, the iterated graph under the operator F k is defined iteratively as follows: F 0 (G) = G and for k ≥ 1, F k (G) = F k-1 (F (G)). We say that a graph G diverges under the operator F whenever lim k→∞ |V (F k (G))| = ∞. We say that a graph G converges under the operator F whenever lim k→∞ F k (G) = F m (G) for some m. We say that a graph G is periodic under the operator F whenever F k (G) = F k+s (G) for some k, s, s ≥ 2.

The iterated biclique graph KB k (G), is the graph obtained by applying iteratively the biclique operator KB k times to G.

In the thesis we will use the terms convergent or divergent meaning convergent or divergent under the biclique operator KB.

By convention, we arbitrarily say that the trivial graph K 1 is convergent under the biclique operator (observe that this remark is needed, since the graph K 1 does not contain bicliques).

Chapter 3 Proper Connection of Graphs

This chapter is organized as follows: In Section 3.1 we study pc k (G) for bipartite graphs. We state a conjecture, prove several small results and finally we prove the conjecture for k = 1, that is, for pc(G). In Section 3.2, we study pc(G) for general graphs and prove non-trivial bounds, improving Vizing's trivial bound of ∆ + 1. Then, motivated by both of these sections, we state a conjecture regarding pc k (G) for general graphs. In Section 3.3 we prove a bound concerning the minimum degree of G.

Bipartite graphs

In this section, we study proper connection numbers in bipartite graphs. We state a general conjecture for pc k (G) where G is a bipartite graph with some specific connectivity that depends on k. Following that, we show that this conjecture is best possible in the sense of connectivity. Later, we prove some results for specific classes of graphs such as complete bipartite graphs with lower connectivity assumptions than that which is required for the conjecture. Then, we prove that the conjecture is true for complete bipartite graphs. Finally, we study the case k = 1 and obtain results for trees and other graphs depending on their connectivity. We end the section by obtaining, as main result, the proof of the conjecture for the special case k = 1 and some corollaries stemming from it.

Conjecture 3.1.1. If G is a 2k-connected bipartite graph with k ≥ 1, then pc k (G) = 2.
If true, Conjecture 3.1.1 is the best possible in the sense of connectivity. In the following we present a family of bipartite graphs which are (2k -1)-connected with the property that pc k (G) > 2. It is also clear that we cannot exchange the vertex connectivity for edge connectivity since it is easy to find graphs with connectivity 1 which have edge connectivity 2k.

Consider the complete bipartite graph G = K p,q with p = 2k -1 (k ≥ 1) and q > 2 p where G = V ∪ W , V = {v 1 , v 2 , . . . , v p } and W = {w 1 , w 2 , . . . , w q }. Clearly, G is (2k -1)connected. We will show that pc k (G) > 2.

Proposition 3.1.2. Let p = 2k -1 (k ≥ 1) and q > 2 p . Then pc k (K p,q ) > 2.

Proof. Suppose that pc k (G) = 2 and consider a k-proper connected coloring of G with 2 colors. For each vertex w i ∈ W , there exists a p-tuple C i = (c 1 , c 2 , . . . , c p ) so that c(v j w i ) = c j for 1 ≤ j ≤ p. Therefore, each vertex w i ∈ W has 2 p different ways of coloring its incident edges using 2 colors. Since q > 2 p , there exist at least two vertices w i , w j ∈ W such that C i = C j . As pc k (G) = 2, there exist k internally disjoint proper paths in G between w i , w j . Using this, we will arrive to a contradiction. First, observe that one of these paths between w i , w j (say P ) must have only one intermediate vertex v l ∈ V since otherwise, if all the paths have at least two intermediate vertices in V , we would have |V | ≥ 2k, which is a contradiction. Hence, as C i = C j we have c(v l w i ) = c(v l w j ) and therefore the path P is not properly colored, leading to a contradiction.

Based on the previous result we prove the following.

Theorem 3.1.3. Let G = K n,3 then pc 2 (G) =      2 if 3 ≤ n ≤ 6 3 if 7 ≤ n ≤ 8 3 √ n if n ≥ 9
Proof. It is easy to check that pc 2 (G) = 2 for 3 ≤ n ≤ 6 and pc 2 (G) = 3 for 7 ≤ n ≤ 8. Now let n ≥ 9. We will give a 2-proper coloring of G using c = 3 √ n colors and we will also show that this is the best possible. Consider the bipartition of

G = V ∪ W such that |V | = n and |W | = 3. Let V = {v 1 , ..., v n } and W = {w 1 , w 2 , w 3 }. For each vertex v i ∈ V , we consider a 3-tuple C i = (c 1 , c 2 , c 3 ) so that c(v i w j ) = c j for 1 ≤ j ≤ 3. Therefore, each vertex v i ∈ V has c 3 different
ways of coloring its incident edges using c colors. We then color the edges of G as follows. If c ≥ 4 then we color the edges of (c -1) 3 vertices of V with all the different triples of c -1 colors and, for the remaining vertices, we choose different triples but this time using the c th color. If c = 3, we just choose different triples of colors but starting with the c! colorings with all three colors different. By this coloring we have that for each pair of vertices v i , v j ∈ V we have that C i = C j for all 1 ≤ i = j ≤ n.

Before proving that this coloring is 2-proper, it is easy to see that G cannot be colored to make it 2-proper connected using fewer than c colors by following the same argument as in Proposition 3.1.2. That is, if we use fewer than c colors, there must exist at least two vertices v i , v j ∈ V such that C i = C j , a contradiction. Now consider two vertices v i , v j ∈ V and we would like show the existence of 2-proper paths between them. Since C i = C j , we know that at least one of the three colors is different. If two or three are different, then we have 2-proper paths of the form v i w k v j and v i w l v j such that c(v i w k ) = c(v j w k ) and c(v i w l ) = c(v j w l ). Suppose now that exactly one of the three colors is different, say c 1 without losing generality, then v i w 1 v j is a proper path. For the second path, there exists a vertex v k ∈ V such that, by construction of the coloring, c

(v i w 2 ) = c(v k w 2 ), c(v j w 3 ) = c(v k w 3 ) and c(v k w 2 ) = c(v k w 3 ). Therefore v i w 2 v k w 3 v j is a proper path between v i and v j .
Next consider w i , w j ∈ W , it is clear that there exist two vertices v k , v l ∈ V such that C k and C l have both colors different to w i , w j . Therefore w i v k w j and w i v l w j are proper paths. Finally, we consider the case where v i ∈ V and w j ∈ W . The edge v i w j provides a trivial proper path. For the second path, simply choose other appropriate vertices v k ∈ V and w l ∈ W such that v i w l v k w k results in a proper path. These vertices exist by the constructed coloring of G. As no cases are left, the theorem holds. Now we prove the conjecture for complete bipartite graphs.

Theorem 3.1.4. Let G = K n,m , m ≥ n ≥ 2k for k ≥ 1. Then pc k (G) = 2
Proof. Take the bipartition of G = A ∪ B. Then split each set A and B into the sets

A 1 , A 2 , B 1 , B 2 such that |A i |, |B i | ≥ k for i = 1, 2
. This is clearly possible since |A|, |B| ≥ 2k. Now color the graph in the following way. Put c(vw) = 1 for all v ∈ A 1 and w ∈ B 1 , and for all v ∈ A 2 and w ∈ B 2 . Finally put color 2 to the rest of the edges, that is, c(vw) = 2 for all v ∈ A 1 and w ∈ B 2 , and for all v ∈ A 2 and w ∈ B 1 (see Figure 3.1). Now we prove that this coloring produces k proper paths between each pair of vertices of G. First, consider two vertices v, w ∈ A 1 (an identical argument holds for pairs in other sets). Since the cardinality of each set is at least k, we form k proper paths vb

1 a 2 b 2 w choosing b 1 ∈ B 1 , a 2 ∈ A 2 and b 2 ∈ B 2 . If v ∈ A 1
and w ∈ A 2 (similarly for v ∈ B 1 and w ∈ B 2 ) we have at least 2k proper paths formed as vbw for each choice of b ∈ B. The final case is when v ∈ A 1 and w ∈ B 1 (that is, v and w are adjacent). Here we have at least k + 1 proper paths, as follows. One path is simply the edge vw while the k that remain are of the form vb 2 a 2 w for each choice of b 2 ∈ B 2 and a 2 ∈ A 2 . This completes the proof. Now we will study the case k = 1, that is pc(G). By König's Bipartite Theorem [START_REF] König | Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre[END_REF] we have that the edge chromatic number is ∆ for bipartite graphs and therefore ∆ is a trivial upper bound for pc(G) for any bipartite graph G. Then, we obtain this trivial corollary.

Corollary 3.1.5. If G is a tree then pc(G) = ∆.

The following theorem is the main result of the section. It improves upon the upper bound of ∆ by König to the best possible whenever the graph is bipartite and 2-edgeconnected.

Theorem 3.1.6. Let G be a graph. If G is bipartite and 2-connected then pc(G) = 2 and there exists a 2-coloring of G that makes it proper connected with the following strong property. For any pair of vertices v, w there exists two paths P 1 , P 2 between them (not necessarily disjoint) such that start(P 1 ) = start(P 2 ) and end(P 1 ) = end(P 2 ).

Given a 2-connected graph G, let G 1 be an instance of the graph G \ P where P is the set of internal vertices of the last ear of an ear decomposition of a G. Similarly, if the graph is 2-edge-connected, there is a (closed) ear decomposition in which an ear may attach to the previous structure at a single vertex. Therefore, using the same argument, one could easily show the result also holds for a 2-edge-connected graph G.

Proof. Suppose G is 2-connected and bipartite and consider a spanning minimally 2connected subgraph (meaning that the removal of any edge would leave G 1-connected).

For the sake of simplicity, we call this subgraph G. This proof is by induction on the number of ears in an ear decomposition of G. The base case of this induction is when G is simply an even cycle and we alternate colors on the edges.

Let P be the last ear added where the ends u and v of P are in G 1 and all internal vertices of P are in G \ G 1 . Since G is minimally 2-edge-connected, we know that the length of P is at least 2. By induction on the number of ears, we obtain a 2-coloring of G 1 so that G 1 has the strong property. Color P with alternating colors. Let C be the proper cycle of G such that C = P P where P is the appropriate proper path in G 1 between u and v. Clearly this path exists, since in G 1 we have the strong property.

Finally we show that this coloring of G is proper connected with the strong property. Every pair of vertices in C has the strong property since C is an alternating even cycle. Also, by induction, every pair of vertices in G 1 has the strong property. Let x ∈ G \ C and let y ∈ P . The pair xu has the strong property so there exists a path Q u from x to u so that xQ u uP y forms a proper path Q u . Similarly the pair xv has the strong property so there exists a path Q v from x to v so that xQ v vP y is a proper path Q v . Since C is a proper cycle, Q u and Q v must have different colors on the edges incident to y. Note also that, since G is bipartite, the parity of the length of Q u is the same as the parity of the length of Q v . Hence, Q u and Q v must also have different colors on the edges incident to x. This shows that x and y have the strong property, thereby completing the proof.

As a result of Theorem 3.1.6 we obtain the following corollary.

Corollary 3.1.7. Let G be a graph. If G is 3-connected, then pc(G) = 2 and there exists a 2-edge-coloring of G that makes it proper connected with the following strong property. For any pair of vertices v, w there exist two paths P 1 , P 2 between them (not necessarily disjoint) such that start(P 1 ) = start(P 2 ) and end(P 1 ) = end(P 2 ).

Proof. By [START_REF] Paulraja | A characterization of Hamiltonian prisms[END_REF], any 3-connected graph has a spanning 2-connected bipartite subgraph. Then the result holds by Theorem 3.1.6

General graphs

We begin this section by studying pc(G) for a general graph G. We show some easy results for specific classes such as complete graphs and cycles. Following this, we prove a result analogous to that obtained in the previous section for 2-connected graphs but using 3 colors instead of 2. We also show that this bound is sharp by presenting a 2-connected graph for which 2 colors are not enough to make it proper connected. As a main result of the section, we state an upper bound for pc(G) for general graphs that can be possibly reached as we saw in the previous section. Based on the results of 2-connected graphs we extend Conjecture 3.1.1 to general graphs and finally we prove this for complete graphs. By Vizing's Theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF], we have that the edge chromatic number of any graph is at most ∆ + 1 and therefore ∆ + 1 is a trivial upper bound for pc(G) for any graph G. First we present some easy results. By using alternating colors, it is easy to see that any path of length at least 2 and any cycle of length at least 4 has proper connection number 2. Also it is clear that the addition of an edge to G cannot increase pc k (G). Fact 3.2.0.2. For n ≥ 3, pc(P n ) = 2 and if n ≥ 4, pc(C n ) = 2. Furthermore, pc k is monotone decreasing with respect to edge addition.

We present now the following proposition.

Proposition 3.2.1. If pc(G) = 2 then pc(G ∪ v) = 2 as long as d(v) ≥ 2.
Proof. Let u, w be two neighbors of v in G. Since we have assumed there is a 2-coloring of G so that G is properly connected, there is a properly colored path P from u to w in G. Color the edge uv so that c(uv) = start(P ) and color vw so that c(vw) = end(P ). Since every vertex of G has a properly colored path to a vertex of P , every vertex has a properly colored path to v through either u or w, thereby completing the proof.

The following theorem improves the Vizing's ∆ + 1 upper bound whenever the graph is 2-connected. This result is a natural extension of Theorem 3.1.6. Theorem 3.2.2. Let G be a graph. If G is 2-connected, then pc(G) ≤ 3 and there exists a 3-edge-coloring of G that makes it proper connected with the following strong property. For any pair of vertices v, w there exist two paths P 1 , P 2 between them (not necessarily disjoint) such that start(P 1 ) = start(P 2 ) and end(P 1 ) = end(P 2 ).

As in Theorem 3.1.6, we note that an edge-connected version of this result is immediate from the proof.

Proof. Suppose G is a 2-connected graph and consider a spanning minimally 2-connected subgraph (meaning that the removal of any edge would leave G 1-connected). For the sake of simplicity, we call this subgraph G. This proof is by induction on the number of ears in an ear decomposition of G. The base case of this induction is when G is simply a cycle and we properly color the edges with at most 3 colors.

Let P be the last ear added in an ear decomposition of G and let G 1 be the graph after removal of the internal vertices of P . Since G is assumed to be minimally 2-connected, we know that P has at least one internal vertex. Let u and v be the vertices of P ∩ G 1 so

P = uu 1 u 2 . . . u p v.
By induction, there is a 3-coloring of G 1 which is proper connected with the strong property. Color the edges of G 1 as such.

Within this coloring, there exist two paths P 1 and P 2 from u to v such that start(P 1 ) = start(P 2 ) and end(P 1 ) = end(P 2 ). If possible, we properly color the path P so that c(uu 1 ) / ∈ {start(P 1 ), start(P 2 )} and c(u p v) / ∈ {end(P 1 ), end(P 2 )}. Note that this is always possible if either P has at least 2 internal vertices or {start(P 1 ), start(P 2 )} ∪ {end(P 1 ), end(P 2 )} = {1, 2, 3}. It will become clear that this is the easier case so we assume this is not the case, namely that P has only one internal vertex x and {start(P 1 ), start(P 2 )} ∪ {end(P 1 ), end(P 2 )} = {1, 2}.

Color the edge xu with color 3 and xv with color 2 (supposing that end(P 2 ) = 2). We will show that this coloring of G is proper connected with the strong property. For any pair of vertices in G 1 , there is a pair of proper paths connecting them with the strong property by induction. Since P ∪ P 1 forms a proper cycle, any pair of vertices in this cycle also have the desired paths. Let y ∈ G 1 \ P 1 and note that our goal is to find two proper paths from x to y with the strong property.

Since y and u are both in G 1 , there exist a pair of paths P u 1 and P u 2 starting at y and ending at u with the strong property. Similarly, there exist two paths P v 1 and P v 2 starting at y and ending at v with the strong property. Since these paths have the strong property, we know that Q 1 = xuP u i y (note that the implied orientation on P u i is reversed when traversing the path from u to y) is a proper path for some i ∈ {1, 2} (suppose i = 1) and similarly Q 2 = xvP v j y is a proper path for some j ∈ {1, 2} (suppose j = 1). These paths form the desired pair if end(Q

1 ) = end(Q 2 ) so suppose start(P v 1 ) = start(P u 1 ). Next consider walk R 1 = xuP 1 vP v 2 y and the path R 2 = Q 2 .
If R 1 is a path, then R 1 and R 2 are the desired pair of paths since end(P 1 ) = c(xv) = end(P v 2 ), meaning that R 1 is a proper walk. Hence, suppose R 1 is not a path and let z be the vertex closest to y on

P v 2 which is in P 1 ∩ P v 2 . Now if the path R 1 = xuP 1 zP v 2 y
is a proper path, then R 1 and R 2 are the desired pair of paths so we may assume that end(uP 1 z) = start(zP v 2 y).

Finally we show that the paths S 1 = xvP 1 zP v 2 y and S 2 = Q 1 = xuP u 1 y are proper paths from x to y with the strong property. Certainly, as noted above, S 2 is a proper path. Also, S 1 is a proper path since P 1 is proper so end(vP

1 z) = end(uP 1 z) = start(zP v 2 y).
Finally since end(zP v 2 y) = start(P v 2 ) = start(P v 1 ) = start(P u 1 ), we see that S 1 and S 2 have the strong property.

It is important to mention that there exist 2-connected graphs with pc(G) = 3 and therefore the bound obtained by Theorem 3.2.2 is reached. Now we give an example (see Fig. 3.2) of such a graph and prove why two colors are not enough. The assumption that each uninterupted segment has length at least 4 is mostly for convenience. Note that the graph G (in Figure 3.2) does not satisfy this condition but it can still be shown that pc(G) = 3 by a similar argument.

Proof. By Theorem 3.2.2, we know that pc(G) ≤ 3 so it suffices to show that pc(G) = 2. Suppose we have a 2-coloring of G which is properly connected. Label the segments of G as in Figure 3.2. Note that we may assume there are no three edges in a row of the same color within an uninterupted segment since we could switch the color of the middle edge (making that subsegment alternating) without disturbing the proper connectivity.

We would first like to show the segments A, B and C are all alternating. If two of these segments are not alternating, suppose A and B, then any vertex in D cannot be properly connected to any vertex of C so this is clearly not the case. This means that at most one segment, suppose A, is non-alternating. Suppose the edges uv and vw have the same color for some u, v, w ∈ A (see Figure 3.3). There must exist a proper path from u to w so suppose there is such a path using the segments F CEBD. Since the following argument does not rely on the parity of this path, this assumption, as opposed to using any of D , E or F , does not lose any generality. Let x be a vertex in the interior of B. We already know there is a proper path from x to v using D. Since D ∪ D forms an odd cycle, there can be no proper path from x to v through D . Let y ∈ E . In order for y to have a proper path to w, it must use the segments BD (as opposed to BD ) and similarly to reach u, it must use CF (as opposed to CF ). Since E ∪ E forms an odd cycle, and yet y can reach both u and w, we know that the edges on either side of y must have the same color. This holds for all y ∈ E , clearly a contradiction. Therefore we know that A, B and C are all alternating segments.

Next we would like to show that at least one of D or D must be alternating (and similarly at least one of E or E and one of F or F ). Suppose D and D are both nonalternating. Let v be an interior vertex in D which has two edges of the same color and let y be a vertex of D with two edges of the same color. Let u and w be the neighbors of v and let x and z be the neighbors of y (see Figure 3.4). Clearly there can be at most one pair (in this case D and D ) in which neither segment is alternating since there must be an alternating path from u to w and it must pass through the other segments. Also, there can be no other pairs of adjacent monochromatic edges within D and D since u, v and w (likewise x, y and z) must have alternating paths out of the segment and we have assumed that there are no three edges of the same color in a row. Note that, in the figure, possibly x = a, u = a, z = b or w = b. If we let c ∈ C, then each of u, w, x and z must have an alternating path to c. Suppose the edge of A incident to a has color 1. Then both edges incident to a in Q must have color 2. This means that both edges of Q which are incident to a must be the same color (and similarly both edges of Q incident to b must have the same color). Therefore, there are exactly 4 vertices in Q for which both edges of Q have the same color. Unless x = a (or possibly z = b, u = a or w = b), this means that Q is even, a contradiction. Suppose x = a so, in order for z = b to have a proper path to w, we must also have w = b, meaning that u = a and z so again Q is even for a contradiction. Hence, we know that at least one of D or D must be alternating (and similarly for the other odd ears). Without loss of generality, suppose D, E and F are all alternating.

Our next goal is to show that Q = A ∪ B ∪ C ∪ D ∪ E ∪ F forms an alternating cycle (with the possible replacement of D with D , E with E or F with F ). As we have shown, the only places where we can have a problem is at the intersections so let a and b be (as before) the end-vertices of D (the same argument may be applied for E or F ) and suppose a is between two edges of the same colors (suppose color 1) on Q. Let u, v, w be the neighbors of a with u ∈ A, v ∈ D and w ∈ D so we have assumed the edges au and aw both have color 1 (see Figure 3.5 where the darker edges represent edges that must have color 1). In order for an alternating path to get from u to w, we must either use D ∪ D or Q (with the possible replacements noted above). If the path uses D , then D ∪ D forms an alternating (and hence even) cycle, a contradiction. Hence, we may assume there is an alternating path from u to w through BECF A (recall again that E may be replaced with E or F with F in this argument). Let x ∈ E . There is an alternating path from u to x and from w to x. Since E ∪ E forms an odd cycle but x has an alternating path through B (to get to w) and through C and A (to get to u), we know that x must have two edges of the same color within E . Since x was chosen arbitrarily, this is clearly a contradiction. This means that Q is an alternating (and hence even) cycle.

Now we simply consider one vertex in each of D , E and F . Since these ears form odd cycles, there exists a vertex in each segment from which (and to which) an alternating path can only go one direction on Q. By the pigeon hole principle, at least two of them must go the same direction, meaning there is no alternating path between them. This completes the proof of Proposition 3.2.3.

If the diameter is small, then the proper connection number is also small. More formally, we get the following result.

Theorem 3.2.4. If diam(G) = 2 and G is 2-connected, then pc(G) = 2.
Proof. If G is 3-connected, Corollary 3.1.7 implies that pc(G) = 2 so we may assume κ(G) = 2. Let C = {c 1 , c 2 } be a (minimum) 2-cut of G and let H 1 , . . . , H t be the components of G \ C. Order components so that there is an integer 0 ≤ s ≤ t such that every vertex of H i is adjacent to both c 1 and c 2 for i > s. Note that if s = 0, we have all edges from C to G \ C so G contains a spanning 2-connected bipartite graph and by Theorem 3.1.6, pc(G) = 2. For each component H i with i ≤ s, define subsets

H i,1 = N (c 1 ) ∩ H i and H i,2 = N (c 2 ) ∩ H i . Since each component is connected and C is a minimum cut, there must be an edge from H i,1 to H i,2 . Let e i = v i,1 v i,2 be one such edge in each component H i . Define the graph G 0 = G[C ∪ ( s i=1 {v i,1 , v i,2 })].
This graph is 2-connected and bipartite so pc(G 0 ) = 2 and notice that |G 0 | = 2 + 2s. Let G 1 be a subgraph of G obtained by adding a vertex to G 0 which has at least 2 edges into G 0 . Furthermore, let G i be a subgraph of G obtained by adding a vertex to G i-1 which has at least 2 edges into G i-1 . By Proposition 3.2.1, pc(G i ) = 2 for all i. We claim that there exists such a sequence of subgraphs of G such that G n-(2+2s) is a spanning subgraph of G. In order to prove this, suppose that G i is the largest such subgraph of G and suppose there exists a vertex v ∈ G \ G i . Certainly every vertex which is adjacent to both c 1 and c 2 is in G i . This means v ∈ H j for some 1 ≤ j ≤ s. Since H j is connected, there exists a path from v i,1 to v within H j . Let w be the first vertex on this path which is not in G i . Since diam(G) = 2, we know that w must be adjacent to at least one vertex of C. This means that d G i (w) ≥ 2 so we may set G i+1 = G i ∪ w for a contradiction. This completes the proof.

Finally we prove an upper bound for pc(G) for general graphs which is best possible as we saw before. Theorem 3.2.5. Let G be a connected graph. Consider ∆(G) as the maximum degree of a vertex which is an endpoint of a bridge in G.

Then pc(G) ≤ ∆(G) if ∆(G) ≥ 3 and pc(G) ≤ 3 otherwise.
Proof. Let B 1 , B 2 , . . . B s be the blocks of G with at least 3 vertices. For each block of B i we have the following cases.

• B i is bipartite or 3-connected: Then by Theorem 3.1.6 and Corollary 3.1.7, B i can be colored with 2 colors having the strong property. We color B i in such a way.

• κ(B i ) = 2: Then by Theorem 3.2.2, B i can be colored with 3 colors having the strong property. We color B i in such a way.

It is easy to see that G is proper connected if there are no more uncolored edges in G since each B i has the strong property. Thus, suppose that there remain uncolored edges in G. It is clear that these edges induce a forest F in G. We color them as follows. Take one of the blocks, say B 1 , which contains a vertex v ∈ B 1 which is incident with some uncolored edges. Clearly, v is an endpoint of a bridge in G. We color these uncolored edges incident to v with different colors starting with color rd B 1 (v) + 1. Then, we have that rd G (v) ≤ ∆(G). We do the same for the rest of the vertices incident to bridges in B 1 . Then, we extend our coloring for each tree going out from B 1 in a Breadth First Search (BFS) way, coloring its edges with different colors (observe from Corollary 3.1.5 that rd G (w) ≤ ∆(G) ≤ ∆ for each vertex w in the interior of a tree) until we reach the rest of the blocks. And finally, for each of these blocks (in this order), we repeat the previous step. Before proving that this coloring makes G proper connected, it is important to mention that, if we reach a block B i with some color c ≥ rd B i (w) + 1, and the corresponding vertex, say w, of B i has more than c-rd B i (w) uncolored incident edges, then, when we color these edges, we do not repeat color c. Also, it is important to remark that, by coloring F in this way, we have that in any path that traverses some block from one tree in F to another, at least one of the colors before or after traversing the block is not used in the block.

We now prove that G is proper connected. Let v, w be vertices of G. It is clear that if both belong to the same block B i , then there exists a proper path between them and the same happens if they belong to the same tree outside the blocks. If v ∈ B i , w ∈ B j and B i ∩ B j = {u}, then there exist two paths P 1 , P 2 between v and u in B i , and two paths P 3 , P 4 between u and w in B j with the strong property. Suppose without losing generality that end(P 1 ) = start(P 3 ) and end(P 2 ) = start(P 4 ), then we obtain the paths P 1 P 3 and P 2 P 4 between v and w. It is clear that start(P 1 P 3 ) = start(P 2 P 4 ) and end(P 1 P 3 ) = end(P 2 P 4 ) since start(P 1 P 3 ) = start(P 1 ) = start(P 2 ) = start(P 2 P 4 ) and end(P 1 P 3 ) = end(P 3 ) = end(P 4 ) = end(P 2 P 4 ). Therefore, these paths are proper. Now, if B i ∩ B j = ∅ and there is a tree T in F such that B i ∩ T = {u 1 } and B j ∩ T = {u 2 }, we form a proper path between v and w as follows. Let P 1 be the unique (proper) path in the tree T between u 1 and u 2 . Let P 2 be the proper path in B i between v and u 1 such that end(P 2 ) = start(P 1 ). This path exists since we have the strong property in each block. Analogously, let P 3 be the proper path in B j between u 2 and w such that end(P 1 ) = start(P 3 ). Finally the path P = P 2 P 1 P 3 is proper between v and w. The same idea applies if v is in a block B i and w is in a tree T in F such that B i ∩ T = {u}.

The idea also applies in the case that v is in a tree T i in F , w is in a tree T j in F and there is a block B such that T i ∩ B = {u 1 } and T j ∩ B = {u 2 }. Finally, the result holds by induction on the number of trees and blocks between vertices v and w using the remark stated before to guarantee the paths always traverse the blocks. Therefore, pc(G) ≤ ∆(G) if ∆(G) ≥ 3 and pc(G) ≤ 3 otherwise.

To end the section, based on the Theorem 3.2.2 and the previous section, we extend the Conjecture 3.1.1 to general graphs.

Conjecture 3.2.6. If G is a 2k-connected graph with k ≥ 1, then pc k (G) ≤ 3.
This conjecture is proved for k = 1 in Theorem 3.2.2. Now we prove a stronger result for complete graphs.

Theorem 3.2.7. Let G = K n , n ≥ 4, and k > 1. If n ≥ 2k then pc k (G) = 2
Proof.

• Case n = 2p for p ≥ 2:

Take a hamiltonian cycle C = v 1 v 2 . . . v 2p of G and alternate colors on the edges using colors 1 and 2 starting with color 1. Color the rest of the edges using color 1.

It is clear that there are p ≥ k edges with color 2. We will prove that this coloring gives us k proper paths between each pair of vertices of G. Take two vertices v, w such that c(vw) = 2. This edge colored with color 2 is one proper path between v and w. Now, since there are at least other p -1 ≥ k -1 edges colored with color 2 and the rest of the edges are colored with color 1, we have at least k -1 proper paths between v and w using these edges. That is, for each vertices v , w such that c(v w ) = 2 we form the proper path vv w w. The case where c(vw) = 1 is similar.

• Case n = 2p -1 for p ≥ 2: Take a hamiltonian cycle C = v 1 v 2 . . . v 2p-1 of G
and alternate colors on the edges using colors 1 and 2 starting with color 1. We have p edges with color 1 and p -1 edges with color 2 so far since c(v

1 v 2 ) = 1 and c(v 1 v 2p-1 ) = 1. Now, put c(v 2 v 2p-1 ) = 2, c(v 1 v 3 ) = 2, c(v 1 v 2p-2 ) = 2

Minimum degree

In this section, we prove a result concerning minimum degrees. For this, we will make use of the following theorems.

Theorem 3.3.1 ([40]). Let G be a graph with n vertices. If δ(G) ≥ n-1 2 , then G has a hamiltonian path. Moreover, if δ(G) ≥ n/2, then G has a hamiltonian cycle. Also, if δ(G) ≥ n+1 2 , then G is hamilton-connected. Theorem 3.3.2 ([110]). Let G be a graph with n vertices. If δ(G) ≥ n+2 2
then G is panconnected meaning that, between any pair of vertices in G, there is a path of every length from 2 up to n -1. For this statement, we use the following notation. For a path

P = v 1 v 2 • • • v , we let endpoints(P ) = {v 1 , v }. Lemma 3.3.5. The following graphs H i , for (i = 1, 2, . . . , 6), have pc(H i ) = 2.
(1) The graph H 1 obtained from a path P with |P | ≥ 2 and m ≥ 0 isolated vertices v 1 , . . . , v m by joining each v i for (i ≤ m) within P with at least two edges.

( By the choice of P 2 , note that P 2 ∩ S = ∅. Let P be a path joining P 1 and P 2 at the common vertex v. Then, utilizing P and the assumption δ(G) ≥ n/4, we will find a spanning subgraph which has a property of H 1 in Lemma 3.3.5. In order to show this, we need only show that each vertex in G \ P has at least 2 edges to P . As previously discussed, we know that all vertices in C 1 have at least 2 edges to P 1 so we need only check vertices x ∈ C 2 \ P is hamilton-connected. Also, by the minimum degree condition and since n ≥ 36, we see that δ(C i ) ≥ (|C i | + 2)/2 for i = 1, 2 so for any vertex z ∈ C i , C iz is hamiltonconnected. By Theorem 3.3.1, C 3 is hamiltonian so it contains a spanning path P with v ∈ endpoints(P ). If |E(v, C i )| ≥ 2 holds for i = 1 or 2 (suppose i = 1), then we can find an even cycle

) 2
| ≤ |C 22 | in C 2 -S. Note that n/4 -|S| ≤ |C 21 | ≤ |C 22 | ≤ (3n/4 -1) -|S| -(n/4 -|S|) = n/2 -1 because δ(G) ≥ n/
C in C 1 ∪ v such that v ∈ C and |C 1 | ≤ |C| ≤ |C 1 | + 1.
Using a hamiltonian path of C 2 ending at v, together with the path P and the even cycle C, we can easily find a spanning subgraph which satisfies the property of H 3 in Lemma 3.3.5, and hence pc(G) = 2. Thus we may assume that

|E(v, C 1 )| = |E(v, C 2 )| = 1. This implies |C 1 | ≥ n/4 + 1, because there is a vertex of C 1 which is not adjacent to v. Then we get |C 3 | ≤ n/2 -3 so δ(C 3 ) ≥ n/4 -1 ≥ (|C 3 | + 1)/2. If |C 3 | is odd, then by Theorem 3.3.1,
C 3 is hamiltonian connected. Hence, we can find an even cycle using all of C 3 and v and a single path through v using all of C 1 and C2. This provides a spanning subgraph satisfying the properties of

H 3 in Lemma 3.3.5. If |C 3 | is even, then δ(C 3 ) ≥ |C 3 |+1 2 = |C 3 |+2
2 so, by Theorem 3.3.2, C 3 is panconnected. Thus we can find an even cycle through v ∪ C 3 which avoids exactly 1 vertex of C 3 again easily providing a subgraph satisfying the conditions of H 3 in Lemma 3.3.5. This shows that pc(G) = 2 and completes the proof of this case. If C 1 and C 2 are both 3-connected, then by Corollary 3.1.7, there is a 2-coloring of each with that strong property. Along with these colorings, we also color all edges between {u, v} and C i with color i. This coloring clearly shows that P C(G) = 2 so we may assume that at least one component C i has 1 ≤ κ(C i ) ≤ 2. Next we will suppose that 1 ≤ κ(C i ) ≤ 2 for both i = 1, 2. In this case, by the minimum degree condition and the fact that G is 2-connected, we may easily show that each component is hamiltonian connected (since n is large) so G is hamiltonian. This means pc(G) = 2.

/4 -1 ≤ |C 1 | ≤ (n -2)/4 ≤ |C 4 | ≤ n/4 + 1. This means that δ(C i ) ≥ |C i | -2 for all i.
(G) = 2. Subcase 2.2: = 3 Since δ(G) ≥ n/4, we have n/4 -1 ≤ |C 1 | ≤ |C 2 | ≤ (5n -4)/12 and δ(C i ) ≥ n/4 -2 so δ(C i ) ≥ 3|C i |+1 5 -2 for i = 1, 2. Since n ≥ 23, this implies that δ(C i ) ≥ |C i |+1 2 for i = 1, 2 so
Finally, if we suppose C 1 is 3-connected while 1 ≤ κ(C 2 ) ≤ 2, each possible case contains a large (almost spanning) subgraph with the properties of H 4 from Lemma3.3.5, meaning that pc(G) = 2. This completes the proof of Theorem 3.3.6.

The minimum degree condition is best possible. To see this, we construct the following graph. Let G i be a complete graph with n/4 vertices for i = 1, 2, 3, 4, and take a vertex

v i ∈ G i for each 1 ≤ i ≤ 4. Let G be a graph obtained from G 1 ∪ G 2 ∪ G 3 ∪ G 4 by

Chapter 4 Strong Edge-Colorings

This chapter is organized as follows: In Section 4.1 we improve known bounds for strong edge-colorings in k-degenerate graphs and chordless graphs. Then we give a polynomial time algorithm to find such colorings. In Section 4.2, we improve known bounds for outerplanar graphs and also, we give polynomial time algorithms to find the colorings.

k-degenerate graphs

In this section, we prove the general result for k-degenerate graphs. In the following, a vertex of degree k is called a k-vertex. Vertices of degree at most k and at least k, are respectively called k --vertex and k + -vertex. An edge incident to a 1-vertex is called a pendant edge. We may use partial coloring or partial strong edge-coloring to denote a strong edge-coloring of a subset of the edges of G. Given a partial coloring, the colored degree of a vertex x denoted cd(x), is the number of colored edges incident to x. The following easy lemma from [START_REF] Chang | Strong chromatic index of 2-degenerate graphs[END_REF] shows a nice structural property of k-degenerate graphs.

Lemma 4.1.1 ([29]). If G is a k-degenerate graph, then there is some v ∈ V (G) such that at least max{1, d(v) -k} of its neighbors are k --vertices.
This implies the following facts. (1) We can construct any k-degenerate graph from the trivial graph, by adding edges pq such that at most k neighbors of p have degree more than k, and degree of q is at most k (in the present graph after adding e).

(2) There is an ordering of edges, such that we can construct any k-degenerate graph from the empty graph, by adding edges in that order where each edge added satisfies the above property in the current graph. Now, we state the main theorem of the section.

Theorem 4.1.2. Let G be k-degenerate, k ≥ 2. Then, χ s (g) ≤ (4k -1)∆ -2k 2 -k + 1.
Proof. We use induction on the number of colored edges of a partial coloring of G. Let B = {1, 2, . . . , (4k -1)∆ -2k 2k + 1} be the set of colors. We assume that, there is a partial strong edge-coloring of t edges added according to the order given above, such that the coloring satisfies the following.

(1) The partial coloring is a strong edge-coloring of the colored subgraph, and draws its colors from B.

(2) For every edge e incident to a vertex of colored degree at most k -1, having the color say c, no edge f at a distance at most one in the original graph is colored c. Note that, while the distance can be through a non-colored edge, both e and f are part of the partial coloring.

Base cases can be easily verified. We now extend the coloring to t + 1 edges and show that the induction hypothesis still holds. Since we add edges according to the order given by Fact 4.1.1.1.(2), we have an uncolored edge e = vw such that, (1) At most k neighbors of v have high colored degree (> k).

(2) Colored degrees of all other neighbors of v except w are at most k and cd(w) ≤ k -1.

Lemma 4.1.3. Let e = vw be an edge chosen to be colored according to the degeneracy order given by Fact 4.1.1.1. [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF]. The number of colored edges within distance 1 from e is at most (4k -1)∆ -2k 2k.

For any vertex x, let α(x) denote the number of colored edges xy with cd(y) ≥ k + 1. Similarly, let β(x) be the number of uncolored edges xy with cd(y) ≥ k.

Proof. Consider the vertex v. By the choice of e, we have α(v) + β(v) ≤ k. If not, once cd(v) becomes k, (which definitely happens in the coloring process since we have more than kα(v) uncolored edges), the remaining uncolored edges incident to v violate the degeneracy order as both endpoints of these edges have colored degree at least k. Thus, if cd(v) ≥ k, then β(v) = 0. Therefore, in the degeneracy ordering (Lemma 4.1.1) this will not happen. See Figure 4.1 for an illustration. Thus the number of colored edges at distance 1 from e through vertex v can be at most

α(v)∆ + β(v)(∆ -1) + (d(v) -(α(v) + β(v)) -1) k ≤ k∆ + (∆ -k -1)k v w < k ≤ k ≤ k < k < k < k < k < k α + β ≤ k α β
(w)∆ + β(w)(∆ -1) + (d(w) -(α(w) + β(w)) -1) (k -1) ≤ (k -1)∆ + ∆ -1 + (∆ -k -1)(k -1)
. Summing up, the maximum number of colored edges within distance 1 from e is upper bounded by k∆

+ (∆ -k -1)k + (k -1)∆ + ∆ - 1 + (∆ -k -1)(k -1) = (4k -1)∆ -2k 2 -k.
Now, since B has strictly more colors, we can always find one color from B to color the edge e such that the partial coloring remains a strong edge-coloring. We only need to verify that the second condition of the induction hypothesis holds after the coloring.

This follows easily, since we ensure that the color selected for e is different from the colors used at any edges incident to any neighbor of v and w. Thus, we can use induction and the result follows.

By substituting k = 2, as a corollary to the above, we get

Corollary 4.1.4. If G is 2-degenerate, then χ s (G) ≤ 7∆ -9.
which improves the earlier upper bound. We also improve the bounds for chordless graphs as follows.

Theorem 4.1.5. If G is chordless, then χ s (G) ≤ 5∆ -5.
Proof. We know that, every minimally 2-connected graph is 2-degenerate, and their minimum degree is 2 [START_REF] Bollobás | Extremal graph theory[END_REF]. A result from Plummer [START_REF] Plummer | On minimal blocks[END_REF] states that a minimally 2-connected graph does not contain chords (chordless) and every 2-connected chordless graph is minimally 2-connected. Using the results from Plummer [START_REF] Plummer | On minimal blocks[END_REF] and Dirac [START_REF] Dirac | Minimally 2-connected graphs[END_REF], the following lemma has been shown in [START_REF] Chang | Strong chromatic index of 2-degenerate graphs[END_REF][START_REF] Muthu | Some graph classes satisfying acyclic edge colouring conjecture[END_REF] Lemma 4. 1.6 ([86]). Every chordless graph G contains some vertex x such that at least d(x) -1 of its neighbors are 2 --vertices.

The rest of the proof uses essentially the same arguments as for the above proof of k-degenerate graphs. The only difference is that, we can always find a vertex having at most one high degree neighbor. Thus, for each newly added edge, the maximum number of unavailable colors is ∆ + 2(∆ -2) + ∆ + ∆ -2 ≤ 5∆ -6. Thus, setting B = {1, 2, . . . , 5∆ -5}, the induction steps goes through and the result follows.

Algorithmic aspects

In this section, we sketch an algorithm to color any k -degenerate graph with (4k -1)∆-2k 2k + 1 colors. The algorithm follows from the proof arguments of Theorem 4.1.2. As in the case of the proof, the algorithm consists of two phases. The first phase, where we compute an ordering of the edges according to which the edges are selected for coloring, and the second phase, where the actual coloring takes place.

First, we identify the sets of vertices S 1 , S 2 , . . . , S , such that S i ∩ S j = ∅, ∪ i=1 S i = V (G), and for all v ∈ S j , we have d(v) ≤ k in the graph G -∪ j-1 i=1 S i . Finding these sets can be done in O(n + m) operations as follows. We assume that the adjacency list of the input graph is given. It is easy to see that we can find the set S 1 in O(n) time. Then we can update the degrees of all vertices in G-S 1 just looking at the neighbors of the vertices in S 1 . While doing this update, if a vertex in G -S 1 has degree lower than or equal to k, we add it to S 2 . This can be done in v∈S 1 d(v). We proceed similarly with S 2 to find S 3 , and so on until we find the sets. It follows that finding the sets S i ,

1 ≤ i ≤ , can be done in O(n + v∈V d(v)) = O(n + m)
. Now, we explain how to compute the required ordering of edges using the sets S i . Let us denote by E(X, Y ) the set of edges having one endpoint in the set X and the other in set Y . Observe that the desired ordering is given by the edges

E(S l , S l ), E(S l , ∪ l-1 i=1 S i ), E(S l-1 , S l-1 ), E(S l-1 , ∪ l-2 i=1 S i ), E(S l-2 , S l-2 ), . . . , E(S 2 , S 2
), E(S 2 , S 1 ), E(S 1 , S 1 ). It is easy to check that this ordering verifies Fact 4.1.1.1.(2). The ordering can be computed easily by checking for each edge the sets where the endpoints belong, which can be done in O(m).

Using the above ordering, we can color the edges using the (4k -1)∆ -2k 2k + 1 colors. Associated to each vertex, we keep a boolean array of size (4k -1)∆ -2k 2k + 1, where the index corresponds to color. Initially, all the entries are initialised to 0. Every time we color an edge e = uv, we select the first color available to both u and v, and then we update the entries corresponding to this color from 0 to 1 for all the neighbors of u and v (in order to guarantee the strong edge coloring condition). We can find an available color in O(k∆) time. The update operation need to be applied to at most d(u) + d(v) vertices, and can be done in O(d(u) + d(v)) = O(∆) time. Since we do this for each edge in the ordering, we obtain the complexity O(k∆m).

Finally, the total complexity of the algorithm is bounded by O(n + k∆m).

Outerplanar graphs

In this section, we give the exact value of χ s (G) for bipartite outerplanar graphs and we also improve the known bound for the general outerplanar case. We introduce some more definitions and notation. A block is a maximal connected component without a cutvertex. A block decomposition of a graph G is a partition of G into its blocks. Notice that, each component is either a maximally 2-connected subgraph or a single edge. We define an end block of a graph as a 2-connected block that contains a unique cut-vertex which separates it from all the other 2-connected blocks (if exists). Notice that this definition of end block differs from the standard notion in order to address some specific issues.

An ear in G to a subgraph H is a simple path P on at least three vertices with endpoints in H such that [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF]. none of the internal vertices of P are contained in H, and (2). P forms an induced cycle with H. An ear decomposition of a 2-connected subgraph is a partition of its edges into a sequence of ears, where the first ear is an induced cycle. It is easily seen that, for a 2-connected outerplanar graph, there is an ear decomposition where each ear contains at least one internal vertex and the endpoints of every ear are adjacent in the preceding graph (if not, the outerplanarity property is affected). Further, notice that, when the graph is bipartite outerplanar, any added ear has an even number of internal vertices. Any such ear (which forms an induced cycle) together with the edges incident to it forms a puffer graph we defined earlier. Thus, we first show an upper bound for the puffer graphs.

Puffer graphs

Note that, to compute the strong chromatic index we suppose that the puffer graph only has pendant edges (no common neighbors forming a triangle) since we can always split any common neighbor of adjacent vertices of the cycle to two pendant edges which does not affect the upper bound.

The following lemma gives bounds for the puffer graphs.

Lemma 4.2.1. Let G be a puffer graph. Let C be its cycle, then we have the following according to the cycle length |C|.

(

) χ s (G) = d(u) + d(v) + d(w) -3 if |C| = 3, u, v, w ∈ C. (2) χ s (G) = max uv∈E(C) d(u) + d(v), if |C| = 4. 1
(

) χ s (G) = 5 if G = C 5 . ( 3
) χ s (G) = max u∈C d(u) + 2 if |C| = 5 4
and either only a single vertex or exactly two vertices at distance 2 have pendant edges.

(

) χ s (G) = max uv∈E(C) d(u) + d(v) -1 if |C| = 5 5
, at least one vertex has at most 1 pendant edge, and not in cases 3) and 4). . Then,

χ s (G) ≤    d(u) + d(v) -1 if d(u) + d(v) ≥ d(x) + d(y) + d(z) -3 d(u) + d(v) -1 + η, otherwise (7) If G = C k , k ≥ 6, then χ s (G) =    3 if k ≡ 0(mod3) 4 otherwise (8) χ s (G) = max uv∈E(C) d(u) + d(v) -1 if G = C, |C| ≥ 6
and even.

(9) Let u, v be the vertices where the max

u 1 v 1 ∈E(C) d(u 1 ) + d(v 2
) is reached and let x, y and z be the consecutive vertices of C not considering u and v where the

min s 1 ,s 2 ,s 3 ∈C d(s 1 ) + d(s 2 ) + d(s 3 ) is attained. Let η = d(x)+d(y)+d(z)-d(u)-d(v)-3 2 . Then, if G = C 7 and |C| ≥ 9 is odd, χ s (G) ≤    d(u) + d(v) -1 if d(u) + d(v) ≥ d(x) + d(y) + d(z) -3 d(u) + d(v) -1 + η otherwise And same bounds plus 1 if |C| = 7.
Proof. The proof is trivial for statements 1) through 4). Statement 5) can also be easily verified.

For 6) we note that every vertex of the cycle has at least 2 pendant edges. Let uvxyz be the vertices of the C 5 in a cyclic order. We color the cycle with colors 1 to 5 starting at the edge uv. Then we color one uncolored incident edge of each vertex with the only possible color among the used ones (keeping the strong coloring property). We color the uncolored edges at x and z respectively from the set of colors used at u and v respectively. Since d(x) + d(y) + d(z) -3 ≤ d(u) + d(v), we notice that there are enough colors left to color the edges incident to y. Since we use only d(u) + d(v) -1 colors, the bound is optimal in this case. Now, suppose that d(u)+d(v) < d(x)+d(y)+d(z)-3. As before, we color the d(u)-3 edges at u and the d(v) -3 edges at v with new colors. Now, we introduce an additional η new colors, and color as many edges incident to both x and z (one can verify that both x and z have at least η uncolored edges in this case). Then for the remaining edges at x we use at most d(x) -3η colors used at u and for the ones at z use at most d(z) -3η colors used at v. As before, it is not difficult to see that we have enough colors left to color the edges incident to y.

For statement 7), we color the cycle in the following way. If k ≡ 0(mod3) we use colors 1, 2 and 3 repeatedly for the cycle and we are done. If k ≡ 1(mod3), we color one edge with color 4 and then repeatedly with colors 1, 2 and 3. Finally, if k ≡ 2( mod 3), we color the first 5 edges with colors 4, 1, 2, 3, 4 and then repeatedly with colors 1, 2 and 3.

For 8), let C = v 1 v 2 v 3 . . . v 2k v 1 be the even cycle of the puffer graph for k ≥ 3. Let u, v ∈ C be two adjacent vertices which attain max u 1 u 2 ∈E(C) d(u 1 ) + d(u 2 ). We use a total of d(u) + d(v) -1 colors to color the whole graph. First, we use at most 5 colors for the edges of the cycle as follows. Color the edges of the cycle v 1 v 2 , v 2 v 3 , . . . , v 2k-4 v 2k-3 repeatedly with colors 1, 2 and 3. Then color the edges v 1 v 2k and v 2k-3 v 2k-2 with color 4. If the edge v 2k-5 v 2k-4 have color 2 then change the color of the edge v 2 v 3 to color 5. Now color the edges v 2k-1 v 2k with the same color as v 2 v 3 and the edge v 2k-2 v 2k-1 with the same color as v 2k-5 v 2k-4 . Observe that the cycle is strong edge-colored with the property that for every odd vertex on it, there are two available colors to use on their uncolored incident edges among the 5 already used colors (to see this, notice that both edges of the cycle at distance 1 from these vertices are always colored the same). So, color those uncolored edges (if there are) incident to the odd vertices of the cycle with these two available colors.

To color the rest of the uncolored edges, first suppose without loss of generality that u ∈ C is an odd numbered vertex. Now, introduce a set of new colors A, where |A| = d(u) -4, and for each odd vertex on the cycle, color its uncolored incident edges with colors from A using the least permissible color. Then do the same for each even vertex on the cycle using another set of new colors B, where |B| = d(v) -2. Finally, suppose that for some vertex v i on the cycle we have some uncolored edges left after using all the colors from its set. We assume without loss of generality that i is even. Since we have uncolored edges at v i , this means that

d(v i ) > d(v). Observe that d(v i ) + d(v i+1 ) ≤ d(u) + d(v) and d(v i ) + d(v i-1 ) ≤ d(u)+d(v). This implies that max{d(v i+1 ), d(v i-1 )} ≤ d(u)+d(v)-d(v i )
(v) -(d(u) + d(v) -d(v i )) = d(v i ) -d(u)
colors from B to color the edges incident to v i . Same argument follows when there is an odd vertex with its degree greater than d(u). We remark that in total we use |A| + |B| + 5 = d(u) + d(v) -1 colors to give this strong edge-coloring which is optimal since d(u) + d(v) -1 is also a lower bound.

Finally, we show 9). Let C = v 1 v 2 v 3 . . . v 2k-1 v 1 be the odd cycle of the puffer graph for k ≥ 4. First, we use at most 5 colors for the edges on the cycle in the following manner. Without lose of generality suppose that v 1 = x, v 2 = y and v 3 = z. Start to color the edges on the cycle from the edge v 1 v 2 with colors 1,2 and 3 repeatedly till the edge v 2k-7 v 2k-6 . Then, color the edges v 2k-1 v 1 with color 3, v 2k-2 v 2k-1 with color 2, v 2k-6 v 2k-5 and v 2k-3 v 2k-2 with color 4 and v 2k-4 v 2k-3 with color 3. Now, if the edge v 2k-8 v 2k-7 (v 1 v 7 in the special case when k = 4) has color 3 then use color 5 for the edges v 2k-8 v 2k-7 (v 1 v 7 for k = 4) and v 2k-5 v 2k-4 , otherwise color the edge v 2k-5 v 2k-4 with the same color as the edge v 2k-8 v 2k-7 (v 1 v 7 for k = 4).

Observe that the cycle is strong edge-colored with the property that, if we consider vertices v 1 , v 2 as a single vertex (say v 2 ) (to emulate the even case), for every alternate vertex on the cycle (originally numbered even) (except for one in the case of k = 4) there are two available colors to use on their uncolored incident edges among the 5 already used colors. Now, color those uncolored edges (if there are) incident to the even vertices of the cycle with these available colors. In the special case of k = 4, one of the vertices have only one available color and therefore we will need one new color more.

Suppose without loss of generality that u has d(u) -4 uncolored edges. First, if

d(u) + d(v) ≥ d(x) + d(y) + d(z) -3,
χ s (G) = max{max uv∈E d(u) + d(v) -1, max uv∈E(C 4 ) d(u) + d(v)}
where C 4 is the set of all cycles of length 4 in G.

Proof. We observe that given an ear decomposition of an outerplanar graph, every ear together with the edges incident to it forms a puffer graph. Adding ears in the order, a new ear joins two adjacent vertices. Since only the edges incident to 2 adjacent vertices of the new ear are precolored, we note that we can simply extend the coloring to the new puffer graph (as the precolored edges all get distinct colors in both cases). The upper bound for outerplanar graphs is now clear by maximising over all puffer graphs and over all pairs of adjacent vertices (the latter is a trivial lower bound). When the graph is bipartite, this gives the exact value as the upper bound matches the trivial lower bound.

The proof itself gives the algorithm to obtain such a coloring, and it is easy to see that it takes sub-quadratic time.

Chapter 5 Proper Hamiltonian Paths in Edge-Colored Multigraphs

This chapter is organized as follows: In Section 5.1 we present some preliminary results that will be useful for the main results. In Section 5.2 we study proper hamiltonian paths in 2-edge-colored multigraphs. Finally, in Section 5.3 we study proper hamiltonian paths in c-edge-colored multigraphs, for c ≥ 3. We remark that this division is because of proper hamiltonian paths in 2-edge-colored multigraphs are just alternating paths in 2 colors, therefore the results are different of those for c ≥ 3 colors. Proof. We can assume that the graph is connected, otherwise it is easy to see that the only possible case to analyze is when G has two components, the first one is two adjacent vertices and the other has n -2 vertices and at least (n-3)(n-4) 2 + 3 edges. Then, the result follows from a theorem in [START_REF] Byer | Edge bounds in nonhamiltonian k-connected graphs[END_REF].

Preliminary results

Let G be a graph of order n. Let M be a maximum matching in G and let U be the set of unmatched vertices. We shall prove that |U | ≤ 2 by contradiction.

Since M is a maximum matching, neither we can add any new edge to M nor we can replace a set of edges in M in order to obtain a new matching in G which is larger than M .

Necessarily, U is an independent set since otherwise you could add a new edge to M to have a new matching that is larger which contradicts M being maximum. First, let us deal with the case where G has odd order.

We shall prove the result depending on the maximum matching between the independent set U = {u 1 , u 2 , u 3 } and the induced subgraph G -U .

We will count the number of edges in E(G), i.e., those edges which cannot be present in E(G) because otherwise the matching M would not be maximum.

Since

m = |E(G)| ≥ (n-3)(n-4) 2 + 4, then |E(G)| ≤ 3n -10.
Let us study the odd case. For n even, the proof runs parallel. Since the graph is connected, we shall prove the result depending on the size of a maximum matching M between the independent set U = {u 1 , u 2 , u 3 } and the induced subgraph G -U .

Case 1:

If | M | = 1
, there is a unique vertex in N (U ) and therefore that there are at least three vertices, u 1 , u 2 , u 3 , of degree 1 in V (G). This leads to a contradiction since the number of edges in E(G) would be at most (n-3)(n-4) 2 + 3 (the edges which are present in a complete graph on n -3 vertices and three more which connect the vertices of degree one to the complete graph), which contradicts the hypothesis of the lemma.

Case 2:

If | M | = 2, then there are two vertices v 1 , v 2 ∈ G -U , v 1 = v 2 , such that u 1 v 1 , u 2 v 2 , u 3 v 2 ∈ E(G)
and N ({u 2 , u 3 }) ⊆ {v 1 , v 2 }, since otherwise we would have a larger matching between the sets U and G -U . And therefore, all edges of type u 2 v and u 3 v, for any v ∈ G -U -{v 1 , v 2 }, are in E(G). Also, {u 1 , u 2 , u 3 } is an independent set, so there are at least 3 more edges in E(G).

Since M is a perfect matching in G -U , the vertices v 1 and v 2 are extremities of some edge in M . If v 1 v 2 ∈ M , then we can replace v 1 v 2 by u 1 v 1 and u 2 v 2 contradicting that M is maximum. Thus, there exist

w 1 , w 2 ∈ G -U -{v 1 , v 2 }, w 1 = w 2 , such that v 1 w 1 , v 2 w 2 ∈ M .
Necessarily, w 1 w 2 ∈ E(G). Otherwise we can replace {v 1 w 1 , v 2 w 2 } by {u 1 v 1 , u 2 v 2 , w 1 w 2 } and obtain a larger matching.

The edge u 1 w 2 is also in E(G) because otherwise we can replace v 2 w 2 in M by u 1 w 2 and u 2 v 2 in order to get a larger matching.

So far we have at least 2(n -5) + 3 + 1 + 1 = 2n -5 edges in E(G).

There are n-7 2 edges, e 1 , e 2 , ..., e n-7

2

, in M -{v 1 w 1 , v 2 w 2 }. We shall study the conditions given by the possible connections between the edges e i , for i = 1, ..., n-7 2 , and the set {w 1 , w 2 }. Necessarily, |N e i ({w 1 , w 2 }) | ≤ 2, ∀i = 1, 2, ..., n-7

2 . Otherwise, we can find a matching of size two, say {f i1 , f i2 }, connecting e i and {w 1 , w 2 } and we can replace

{e i , v 1 w 1 , v 2 w 2 } by {u 1 v 1 , u 2 v 2 , f i1 , f i2 }.
We can assure then that there are at least n -7 new edges in E(G). By adding up these edges to the 2n -5 edges we have obtained before, we already count 3n -12 edges in E(G).

We shall study two different subcases. First of all, if N (v 1 ) ∩ {u 2 , u 3 , w 2 } = ∅, then 3 new edges are shown to be in E(G). By adding up these new edges to the ones we have counted previously, we have 3n -12 + 3 = 3n -9 edges in E(G). This number is larger than 3n -10, which was the maximum number of edges in E(G) allowed from the lemma's hypothesis and the result follows.

Otherwise, if

N (v 1 ) ∩ {u 2 , u 3 , w 2 } = ∅, then u 1 w 1 ∈ E(G) because, if for example u 2 v 1 ∈ E(G), we can replace v 1 w 1 in M by {u 1 w 1 , u 2 v 1 }, so one more edge is in E(G). Now if u 2 v 1 or u 3 v 1 are in E(G) then all edges of type u 1 v, for any v ∈ G-U -{v 1 , v 2 }, are in E(G) since | M | = 2.
Therefore both u 2 v 1 and u 3 v 1 are missing, or n-5-2 = n-7 (since we have already counted u 1 w 1 and u 1 w 2 ) edges are missing. In the first case we arrive to 3n-9, a contradiction, in the second case we have that 3n-11+n-7 = 4n-18 > 3n-10 and again a contradiction.

Case 3:

If | M | = 3, then there are three distinct vertices v 1 , v 2 , v 3 ∈ G -U , such that u i v i ∈ E(G) for i = 1, 2, 3.
Since there is a perfect matching in G -U , the vertices v 1 , v 2 and v 3 are extremities of some edge in M . If v i v j ∈ M , then we can replace v i v j by u i v i and u j v j contradicting that M is maximum. Thus, there exist three distinct vertices

w 1 , w 2 , w 3 ∈ G -U -{v 1 , v 2 , v 3 }, such that v 1 w 1 , v 2 w 2 , v 3 w 3 ∈ M .
Necessarily, w i w j ∈ E(G) for all i, j = 1, 2, 3. Otherwise we can replace v i w i and v j w j by u i v i , u j v j and w i w j and obtain a larger matching. In the same way, u i w j ∈ E(G) for all i, j = 1, 2, 3, i = j, because otherwise we can replace v j w j by {u j v j , u j v j }. Since U is an independent set, thus there are at least 3 + 3 + 6 = 12 edges in E(G).

If u i w i ∈ E(G) then N (v i ) ∩ {u j , w j } = ∅ for j = i. Otherwise, if for example u j v i ∈ E(G), we can replace v i w i in M by u i w i and u j v i . Thus, there are 3 more edges in E(G). Now, there are n-9 2 edges, e 1 , e 2 , ..., e n-9

2

, in M -{v 1 w 1 , v 2 w 2 , v 3 w 3 }. We shall study the conditions given by the possible connections between the edges e i , for i = 1, ..., n-9 2 , and the sets

U = {u 1 , u 2 , u 3 } and W = {w 1 , w 2 , w 3 }. Necessarily |N e i (W ) | ≤ 3, ∀ i = 1, 2, ..., n-9
2 . Otherwise, we can find a matching of size two, say {f ij , f ik }, j, k ∈ {1, 2, 3}, connecting e i and {w j , w k }, and we can replace

{e i , v j w j , v k w k } by {u j v j , u k v k , f ij , f ik }. Also |N e i (U ) | ≤ 3, ∀ i = 1, 2, ..., n-9
2 . Otherwise, we can find a matching of size two, say {g ij , g ik }, j, k ∈ {1, 2, 3}, connecting e i and {u j , u k }, and we can replace e i by { g ij , g ik }.

We can assure then that there are at least 2 • 3 • n-9 2 = 3n -27 new edges in E(G). By adding up these edges to the 15 edges we have obtained before, we already count 3n -12 edges in E(G).

Recall that we have denoted p i and q i the extremities of e i . Without loss of generality, let us assume that if |N e i (u j ) | = 1, ∀ i = 1, 2, ..., n-9

2 and j = 1, 2, 3 , then N e i (u j ) = p i . Thus either |N e i (U ) | ≤ 1 or N q i (U ) = ∅ for all i = 1, 2, 3. Otherwise we can find a matching of size 2 between U and e i and we again can find a larger matching. Now, for n ≥ 15, there are at least 3 edges in M -{v 1 w 1 , v 2 w 2 , v 3 w 3 }. If N e i (U ) = ∅, then 3 more edges are in E(G) and by adding up these new edges to the 3n -12 that have already found and the result follows. If |N e i (U ) | = 1, then either there exists j = i such that N e i (U ) = N e j (U ) or N e i (U ) = N e j (U ) for all i = j. In the first case q i q j ∈ E(G) and either p 1 u 1 or p 1 q 2 is in E(G). We again have 3 new edges in E(G) and the proof is finished. In the later case all edges connecting the edges in M -{v 1 w 1 , v 2 w 2 , v 3 w 3 } and U have a common vertex, say u 1 . Again, at least 3 more edges are in E(G).

Just one case is left to be studied: if N q i (U ) = ∅, then q i q j ∈ E(G) for all i = 1, 2, 3 and we also get 3 new edges in E(G).

The proof is now finished. Observe also that m i ≥ (n-3)(n-4) 2 + 4 for i ∈ {r, b}, since this threshold is tight when the multigraph is complete on one of the colors.

Let us see the case when n is odd. By Lemma 5.1.1, there exist two matchings M r and M b size n-1 2 , so the result follows straightforward. Let us see now the case when n is even. Then, again by Lemma 5.1.1, there exist two matchings, M r and M b , of size at least n-2 2 . We shall prove the result by contradiction. Let us consider the monochromatic subgraphs in color r and b and suppose that

|M r | = |M b | = n-2
2 . Let U = {u 1 , u 2 } denote the independent set of unmatched vertices in M r . The vertices u 1 and u 2 are connected to the edges in M r . We claim that there exist two distinct vertices

v 1 , v 2 in V (G) -{u 1 , u 2 } such that u 1 v 1 , u 2 v 2 ∈ E r (G c ). Otherwise, if N r ({u 1 , u 2 }) = v 1 ,
this vertex is the extremity of some edge v 1 w 1 in M r and then we distinguish two cases. First, if N r (w 1 ) = v 1 , we have three distinct vertices of degree one which leads us to a contradiction with the total number of edges. Second, there exists w 2 ∈ N r (w 1 ) -{v 1 } and v 2 , such that v 2 w 2 ∈ M r . Then we can replace {v 1 w 1 , v 2 w 2 } by {u 1 v 1 , w 1 w 2 }. After this permutation, we have a new matching on same size but u 1 is replaced by v 2 . So, as we claimed, there always exist two distinct vertices

v 1 , v 2 in V (G) -{u 1 , u 2 } such that u 1 v 1 , u 2 v 2 ∈ E r (G c ) (u 2
and v 2 are those vertices in the case we have just seen). Now, the edge v 1 v 2 is not in M r , since otherwise, we can replace it by {u 1 v 1 , u 2 v 2 } and get a larger matching in color r, contradicting that M r is maximum.

So, there are two vertices w 1 and

w 2 in V (G) -{u 1 , u 2 , v 1 , v 2 } such that v 1 w 1 , v 2 w 2 ∈ M r .
Observe that there can be at most two edges connecting the endpoints of any edge in M r to the set {u 1 , u 2 }, i.e., there are at least two missing edges for each edge in M r , in total 2 n-2 2 . Similarly, for w 1 and w 2 , we have same constraints and therefore, this also means two missing edges for each edge in M r -{v 1 w 1 , v 2 w 2 }, in total 2 n-6

2 . Otherwise, suppose that there is an edge v 3 w 3 with three edges between its endpoints to the vertices w 1 and w 2 , so we can replace v 1 w 1 and v 2 w 2 by say w 1 v 3 , w 2 w 3 , v 1 u 1 and v 2 u 2 to obtain a perfect matching. Finally, as u 1 and u 2 are independent, the edge u 1 u 2 is missing. If we sum up these numbers, there are at least (n -2) + (n -6) + 1 = 2n -7 missing edges in color red.

Same reasoning can be done with the matching M b to obtain 2n -7 blue missing edges. So, the total number of missing edges in colors red and blue is 4n -14. Since the complement of G c has edge set of size less than or equal to 3n -10, for n ≥ 6 we have contradiction. and therefore, the result holds.

Lemma 5.1.3. Let G c , c ≥ 2 be a connected c-edge-colored multigraph. Suppose that G c contains a proper path P = x 1 y 1 x 2 y 2 . . . x p y p , p ≥ 2, such that each edge x i y i is red. If G c does not contain a proper cycle C with vertex set {x 1 , y 1 , x 2 , y 2 , . . . , x p , y p }, then there are at least (c -1)(2p -2) missing edges in G c . Proof. Let P = x 1 y 1 x 2 y 2 . . . x p y p be a proper path, p ≥ 2, such that each edge x i y i is red. Let blue be another color.

The blue edge x 1 y p can not be in G c , otherwise C = x 1 y 1 . . . x p y p x 1 is a proper cycle. Suppose that the blue edges x 1 x i are present in G c , for i = 2, . . . , p. Then, the blue edges y i-1 y p can not be in G c , otherwise we have the proper cycle C = x 1 x i . . . y p y i-1 . . . x 1 that contradicts our hypothesis. Therefore for each edge y i-1 x i in the path, either the blue edge x 1 x i or the blue edge y i-1 y p is missing. So there are 2p-2 2 blue missing edges. Now, suppose that the blue edges x 1 y i are present in G c , for i = 3, . . . , p -2. Then, the blue edges x i+1 y p cannot be in G c at same time as x i y i+1 , y i-1 x i+2 or y i-1 y i+1 , x i x i+2 , otherwise we have the following proper cycles: x 1 y i x i y i+1 x i+1 y p . . . x i+2 y i-1 . . . x 1 or x 1 y i x i x i+2 . . . y p x i+1 y i+1 y i-1 . . . x 1 . The minimum in this case corresponds to one missing edge x i+1 y p for each edge y i-1 x i in the path, for i = 2, . . . , p -1. Therefore, there are 2p- 6 2 blue missing edges. For the moment we have 2p -3 blue missing edges. To obtain the last missing edge suppose that the blue edge x 2 y p is present in G c . Then, it can not be at same time with x 1 y 2 , y 1 x 3 or x 1 x 3 , y 1 y 2 , otherwise we obtain the proper cycles C = x 1 y 2 . . . x 2 y p . . . x 3 y 1 x 1 or C = x 1 x 3 . . . y p x 2 . . . y 2 y 1 x 1 . The minimum in this case corresponds to one missing edge x 2 y p . We remark that the blue edges x 2 y p , y 1 y 2 and y 1 x 3 were not counted before. The edges x 1 x 3 and x 1 y 2 were supposed to exist, otherwise, to obtain the last missing edge we consider the symmetric case, i.e., using the blue edge y p-1 x 1 (if exists).

In total there are 2p-2 2 + 2p-6 2 + 2 = (2p -2) blue missing edges in G c . As we have c -1 colors different from red, that gives us (c -1)(2p -2) missing edges as desired.

Note that this number of missing edges is the same as in the simplest case, this is, if all edges different from red x 1 x i and x 1 y i , for i = 2, . . . , p are not present in G c . Proof. Before starting the proof, we remark that the edges x 1 y 1 and x p y p are of color red. Otherwise, we can easily extend the path by adding an edge of the matching to P . Suppose first that n is even and 2p < n. Since M has size n 2 there are n-2p 2 red edges outside P . Let us denote these edges by e i for i = 1, . . . , n-2p 2 . Suppose there is no proper C cycle such that V (C) = V (P ). Let blue be an another color. By Lemma 5.1.3 there are (2p -2) blue missing edges. As the path is maximum, we cannot extend P having an edge e i neither at the beginning nor at the end of it, then there are no blue edges between the vertices x 1 , y p and the edges e i . Therefore, there are 4 n-2p 2 blue missing edges. Finally, As we cannot add any edge e i in-between the path then there at most 2 blue edges between the edges e i and the edges y i x i+1 , i = 1, . . . , p -1. So, there are 2 n-2p

2 2p-2 2
blue missing edges different from red. Adding up and simplifying all these numbers and having c -1 colors different from red, we arrive that there are (n -2 + pn -2p 2 )(c -1) missing edges in G c different from red. If we search the minimum value of this function we arrive to (2n -4)(c -1) for p = n-2 2 and case (1a) holds. Now if there is a proper cycle C such that V (C) = V (P ) then there cannot exist any edge at all different from red between all vertices of C and the edges e i and therefore there are 2 n-2p 2 2p(c -1) = (2pn -4p 2 )(c -1) missing edges different from red. Again, minimizing the function we obtain the same result as above and case (1b) holds.

Suppose now that n is odd, M = n-1 2 and 2p < n -1, or n is even, M = n-2 2 and 2p < n -2. In both cases, same arguments as before apply just replacing n with n -1 or n -2 respectively, in the number of missing edges. This is because we have n -1 matched vertices and one non-matched vertex for the first case and n -2 matched vertices and two non-matched vertices for the second one. Proof. By a theorem in [START_REF] Byer | Edge bounds in nonhamiltonian k-connected graphs[END_REF], a 2-connected graph on n ≥ 10 vertices and m ≥ (n-2)(n-3) 2 +5 edges, has a hamiltonian cycle. So, if we add a new vertex v to G, joined to all its vertices, we have that G + {v} has m ≥ (n-2)(n-3) 2 + 3 + n = (n-1)(n-2) 2 + 5 edges. Therefore, G + {v} has a hamiltonian cycle, i.e., G has a hamiltonian path and this implies that there exists a matching M in G of size |M | = n 2 .

2-edge-colored multigraphs

In this section we study the existence of proper hamiltonian paths in 2-edge-colored multigraphs. We present two main results. The first one involves the number of edges, and the second one involves the number of edges and the rainbow degree. Both results are tight.

Theorem 5.2.1. Let G c be a 2-edge-colored multigraph on n ≥ 8 vertices. If m ≥ (n -2)(n -3) + 2(n -2) + 2, then G c has a proper hamiltonian path.
Proof. The proof is by induction on n. For n = 8, 9, by a tedious analysis, the result can be shown. Suppose now that n ≥ 10. Observe that E(G c ) ≤ 2n -4. By a Theorem of [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], if for every vertex v ∈ G c we have that d r (v) ≥ n+1

(n -2)(n -3) + 2(n -2) + 2 - (n -1) -( n+1 2 -1) -(n -3) -(n -3) -2 edges.
This number is greater or equal than (n -4)(n -5) + 2(n -4) + 2, i.e., the number of edges required to have a proper hamiltonian path in a graph on n -2 vertices. So, by the inductive hypothesis G c has a proper hamiltonian path P . Finally, as we have chosen the appropriate edges to remove at u and w it is easy to extend P to a proper hamiltonian path for G c . Suppose now that there does not exist two neighbors of v, say u and w, such that c(vu) = r and c(vw) = b. So, we have two possible cases. First case is when v has one only neighbor w in both colors. It is easy to observe that G cv has (n -2)(n -3) + 2(n -2) = (n -1)(n -2) edges, i.e., it is a rainbow complete multigraph. Therefore, we have any possible proper hamiltonian path, in particular the one that starts at w and then we easily extend the path to G c . For the second case, v has just neighbors in one color, say b. Observe that for every vertex w = v, w has a red neighbor different of v. Otherwise, if there is a vertex w without red neighbors, we have that E(G c ) ≥ n -1 + n -2 > 2n -4, a contradiction. Now, suppose first that v has at most n -2 blue neighbors. So, take a neighbor w of v and remove all its blue incident edges. Remove then v from G c and call this graph G c . In G c , w is monochromatic in red, and

G c has at least (n -2)(n -3) + 2(n -2) + 2 -(n -2) -(n -2)
edges. This number is exactly (n-3)(n-4)+2(n-3)+2, i.e., the number of edges required to have a proper hamiltonian path in a graph on n -1 vertices. Then, by inductive hyphothesis in G c we obtain a proper hamiltonian path that clearly starts at w since it was monochromatic. Therefore we have a proper hamiltonian path for G c . Finally, if v has n -1 blue neighbors, suppose that one neighbor w of v has at most n -3 blue neighbors, then we proceed as before, we remove v from the graph and we remove all blue incident edges to w. This graph

G c has at least (n -2)(n -3) + 2(n -2) + 2 -(n -1) -(n -3) = (n -3)(n -4) + 2(n -3) + 2 edges.
Again we obtain a proper hamiltonian path for G c and therefore a proper hamiltonian path for G c (since w is monochromatic in red). Now, every vertex w has n -2 neighbors, i.e., the graph G cv is complete in blue. Call this graph G c . Now, G c has at least (n -2)(n -3) + 2(n -2) + 2 -(n -1) = n 2 -4n + 5 edges and since this is bigger than (n -3)(n -4) + 2(n -3) + 2 by inductive hypothesis we have a proper hamiltonian path in G c . Now, if n -1 is odd, one of the extremities of the path is red and therefore we trivially add v to the path. If n -1 is even, both extremities have the same color. If they are red we are done. Otherwise, remove all the blue edges from G c , this new (red) graph has n -1 vertices and at least n 2 -4n + 5 -(n-1)(n-2) 2 = (n-2)(n-3) 2 + 1 edges therefore by a theorem in [START_REF] Byer | Edge bounds in nonhamiltonian k-connected graphs[END_REF], it has a hamiltonian path P . Now, since G c is complete in blue we can use those blue edges along with P to form a proper hamiltonian P for G c that starts and ends with color red. Finally, we can trivially add v to P .

Since we covered all cases, the proof is finished.

Theorem 5.2.1 is the best possible for n ≥ 8. In fact, consider a rainbow complete 2-edge-colored multigraph on n -2 vertices for n odd. Add two new vertices x 1 and x 2 . Then add the red edge x 1 x 2 and all red edges between {x 1 , x 2 } and the complete graph. Although the resulting graph has (n -1)(n -2) + 2(n -2) + 1 edges, it has no proper hamiltonian path, since at least one of the vertices x 1 or x 2 cannot be attached to any such path. Indeed, for n odd, the first and last edge of any proper hamiltonian path must differ in colors. If n = 5, 7, Theorem 5.2.1 does not hold for the graphs H 2 k,k+3 , k = 1, 2.

Theorem 5.2.2. Let G c be a 2-edge-colored multigraph on n ≥ 14 vertices. Suppose that for every vertex x in G c , rd(x) = 2. If m ≥ (n -3)(n -4) + 3n -2, then G c has a proper hamiltonian path.

Proof. Let us suppose that G c has not a proper hamiltonian path. We will show that E(G c ) has more than 3n -10 edges, i.e., G c has less than (n -3)(n -4) + 3n -2 edges, contradicting the hypothesis of the theorem. We distinguish between two cases depending on the parity of n.

• Case A: n is even. By Lemma 5.1.2, G c has two matchings M r , M b , such that

|M r | = n 2 and |M b | ≥ n-2 2 .
Take the longest proper paths, say, P = x 1 y 1 x 2 y 2 . . . x p y p and P = x 1 y 1 x 2 y 2 . . . x p y p compatibles with M r and M b , respectively. Observe that as the length of P (P ) is odd then both its first and last edges are on the same color. It follows that, since |M r | = n 2 , c(x 1 y 1 ) = c(x p y p ) = r. Otherwise, we can easily extend P by adding an edge of M r . It follows that the edges x i y i are red, i = 1, . . . , p. Similarly, we may suppose that c(x 1 y 1 ) = c(x p y p ) = b. Indeed if c(x 1 y 1 ) = c(x p y p ) = r, then either x 1 or y p is the endpoint of an edge of M b -P and therefore to obtain a path longer that P compatible with M b , a contradiction to the definition of P .

Notice now that if 2p = n or 2p = n, then we are finished. In addition, if 2p < n -2 or 2p < n-2, then by Lemma 5.1.4, there are at least 2n-4 blue missing edges and 2n-8 red ones. This gives a total of 4n-12 > 3n-10 missing edges, a contradiction. Consequently, in what follows we may suppose that 2p = 2p = n -2.

Suppose first that there exists a proper cycle C in G c such that V (C) = V (P ). Let e be the red edge of M r in G c -C. If there exists a blue edge, say e , between an endpoint of e and C, we can easily obtain a proper hamiltonian path considering e, e and a segment of C of length n -3 in the appropriate direction. Otherwise, as the graph is connected, all edges between the endpoints of e and C are red. Now, as rd(G c ) = 2, there must exist a blue edge, say e , parallel to e and therefore we can obtain a proper hamiltonian path just as before but starting with e .

Next suppose that there exists no proper cycle C in G c such that V (C) = V (P ). By Lemma 5.1.4, there are at least 2n -4 blue missing edges. Consider now the path P and let v 1 , w 1 be the vertices in G c -P . It is clear that if there exists a blue edge joining v 1 and w 1 , then by symmetry on the colors there are at least 2n -4 red missing edges. This gives a total of 4n -8 missing edges, a contradiction. Otherwise, assume that there is no blue edge between v 1 and w 1 . In this case we will count red missing edges assuming that we cannot extend P to a proper hamiltonian path. If there exists no cycle C in G c such that V (C ) = V (P ) then by Lemma 5.1.3 there are 2p -2 = n -4 red missing edges. By summing up, we obtain 2n -4 + n -4 = 3n -8 > 3n -10 missing edges, a contradiction. Finally, assume that there exists a proper cycle C in G c such that V (C ) = V (P ). Set C = c 1 c 2 . . . c 2p c 1 where c(c i c i+1 ) = r for i = 1, 3, . . . , 2p -1. If there are 3 or more red edges between {v 1 , w 1 } and {c i , c i+1 }, for some i = 1, 3, . . . , 2p -1, then either the edges v 1 c i and w 1 c i+1 , or v 1 c i+1 and w 1 c i are red. Suppose v 1 c i and w 1 c i+1 are red. In this case, the path v 1 y i x i . . . y i+1 x i+1 w 1 is a hamiltonian one. Otherwise, if there are no 3 or more red edges between {v 1 , w 1 } and {c i , c i+1 }, for all i = 1, 3, . . . , 2p -1, then there are 2 2p -2 2 = n -4 red missing edges. If we sum up we obtain a total of 2n -4 + n -4 = 3n -8 > 3n -10 missing edges, a contradiction.

• Case B: n is odd. By Lemma 5.1.2, G c has two matchings M r , M b , such that

|M r | = |M b | = n-1 2 .
As in Case A, we consider the longest proper paths P and P compatibles with the matchings M r and M b respectively. Suppose first that 2p < n -1 and 2p < n -1. By Lemma 5.1.4, there are at least 2n -6 blue missing edges and 2n -6 red ones. We obtain a total of 4n -12 > 3n -10 missing edges, a contradiction.

Suppose next 2p = 2p = n -1 (the cases where 2p < n -1 and 2p = n -1, or 2p = n -1 and 2p < n -1 are similar). In the rest of the proof, because of symmetry, we will consider only the path P since same arguments may be applied as well for P . In this case we will count blue missing edges assuming that we cannot extend P to a proper hamiltonian path. Now, let v be the unique vertex in G c -P . It is clear that if there is a proper cycle C in G c such that V (C) = V (P ), we can trivially obtain a proper hamiltonian path since the graph is connected, i.e., there is at least one edge between v and C. So, as there is no proper cycle C in G c such that V (C) = V (P ), we have by Lemma 5.1.3, that there are 2p -2 = n -3 blue missing edges. If there exists a blue edge between x 1 and x i , for some i = 2, . . . , p, then it cannot exist the blue edge vy i-1 , otherwise we obtain the proper hamiltonian path vy i-1 . . . x 1 x i . . . y p . We can complete the argument in a similar way, if both edges y p y i and vx i+1 , i = 1, . . . , p -1 exist in G c and are on color blue. Note that since there is no proper cycle C in G c such that V (C) = V (P ), we cannot have at the same time the blue edges x 1 x i and y p y i-1 , i = 2, . . . , p. Therefore, there are 2p-2 2

= n-3 2 blue missing edges. If we make the sum and multiply it by two (since the same number of red missing edges is obtained with P ), we conclude that there are 2(n -3 + n-3

2 ) = 3n -9 missing edges, a contradiction.

Since we covered all the cases, the theorem is proved.

Theorem 5.2.2 is the best possible for n ≥ 14. Indeed, for n odd, n ≥ 14, consider a complete blue graph, say A, on n -3 vertices. Add 3 new vertices v 1 , v 2 , v 3 and join them to a vertex v in A with blue edges. Finally, superpose the obtained graph with a complete red graph on n vertices. Although the resulting 2-edge-colored multigraph has (n -3)(n -4) + 3n -3 edges, it has no proper hamiltonian path since one of the vertices v 1 , v 2 , v 3 cannot belong to such a path. For n = 7, 9, 11, 13, it is easy to see that the graphs H c k,k+3 , k = 2, 3, 4, 5, are exceptions for Theorem 5.2.2.

c-edge-colored multigraphs, c ≥ 3

Finally, in this section we study the existence of proper hamiltonian paths in c-edgecolored multigraphs, for c ≥ 3. We present three main results. The first one involves the total number of edges. The second one, the total number of edges and the connectivity of the graph. The last one, the total number of edges and the rainbow degree. All results are best possible. First, we will present a result that allows us to consider just the case c = 3.

G c ) = k, then rd(G c-1 ) = k -1 for 1 ≤ k ≤ c.
Proof. Let c i denote the color i, for i = 1, . . . , c, in G c , and denote by |c i | the number of edges with color i. Let c j be the color with less number of edges. Color the edges on color c j with another used color, say c l , and delete (if necessary) parallel edges with that color. Call this graph G c-1 . By this, we delete at most |c j | edges. It is clear that this graph is connected since we delete just parallel edges. Also, if is G c-1 has a proper hamiltonian path, then, this path is also proper hamiltonian in G c but maybe with some edges on color c j (in the case that they have been recolored with c l ). Observe also that if rd(G c ) = k then rd = (G c-1 ) = k -1 since only the color c j disappeared. We will show now that m ≥ (c -1) f (n) + 1. We have two cases. First, if

|c j | > f (n), then clearly m ≥ (c -1) f (n) + 1 edges since for all i, |c i | > f (n).
For the second case, we have that

|c j | ≤ f (n). Now, m = c i=1 |c i | ≥ c f (n) + 1 and therefore c i=1,i =j |c i | ≥ c f (n)-|c j |+1 = (c-1) f (n)+f (n)-|c j |+1. This last expression is greater or equal than (c -1) f (n) + 1 since f (n) -|c j | ≥ 0. Finally, we have that G c-1 has m ≥ (c -1) f (n) + 1 edges as desired. Theorem 5.3.2. Let G c be a c-edge-colored multigraph on n vertices, n ≥ 2 and c ≥ 3. If m ≥ c(n-1)(n-2) 2 + 1, then G c has a proper hamiltonian path.
Proof. By Lemma 5.3.1 we can assume that c = 3 and m ≥ 3(n-1)(n-2) 2 + 1. Furthermore, cases n ≤ 7 can be checked by exhaustive methods. Assume so, n ≥ 8. Since there exists one color, say red, such that the number of red edges are at least (n-1)(n-2) 2 + 1 then by a theorem in [START_REF] Byer | Edge bounds in nonhamiltonian k-connected graphs[END_REF], there is a hamiltonian red path and therefore a perfect or almost perfect matching M r . Take the longest proper path P = x 1 y 1 x 2 y 2 . . . x p y p compatible with M r . So we have that, c(x i y i ) = r for i = 1, . . . , p. As m ≥ 3(n-1)(n-2) 2 + 1, |E(G c )| ≤ 3n -4. Now, we will distinguish between two cases depending on the parity of n.

Case A: n even. Clearly |M r | = n 2 . By contradiction suppose that 2p < n, otherwise we are finished. Assume first that there is no proper cycle C in G c such that V (P ) = V (C). By Lemma 5.1.4, there are at least 2(n -2 + pn -2p 2 ) missing edges different from red and therefore the inequality 2(n-2+pn-2p 2 ) ≤ 3n-4 must be satisfied. This inequality does not hold for n ≥ 8. Therefore, we have a contradiction with the number of edges of G c . Assume next that there is a proper cycle C in G c such that V (P ) = V (C). Again by Lemma 5.1.4, 2(2pn -4p 2 ) ≤ 3n -4 must be satisfied, and as before this is never possible for n ≥ 8.

Case B: n odd. Clearly |M r | = n-1 2 . Assume first that there is a proper cycle C in G c such that V (P ) = V (C). If 2p = n-1 then we can obtain a proper hamiltonian path by just taking any edge between the only vertex outside C and C and then following C in the appropriate direction. Otherwise by Lemma 5.1.4 there are 2(2pn -2p -4p 2 ) missing edges different from red and therefore 2(2pn -2p -4p 2 ) ≤ 3n -4 must hold and this never happens for n ≥ 9.

Assume next that there is no proper cycle C in G c such that V (P ) = V (C). If 2p < n -1 the again by Lemma 5.1.4 the inequality 2(n -2 + pn -2p 2 ) ≤ 3n -4 must be satisfied. However this is not possible for n ≥ 9. It remains to handle the case 2p = n -1. Let v be the unique vertex of G c -P . We have the following cases depending on the degree and neighbors of v.

Subcase B1: All edges incident to v are in the same color, say red. We have these situations. First, d(v) ≤ n -2, consider the G c -{v} and delete from a neighbor of v, say w, all edges in two colors in order to have w monochromatic not in red. Call this graph G c . Observe that we can always do this since, it is impossible to have 2 monochromatic vertices. So, by this, we delete at most n-2+n-2+n-2 = 3n-6 edges. It is easy to see that the graph G c on n -1 vertices has at least (n-1)(n-2) 2 + 1 -(3n -6) = (n-2)(n-3) 2 + 1, then, by even case, we have a proper hamiltonian path P in G c . Since w is monochromatic not in red, w is either in the beginning or in the end of P and therefore it is trivial to add v to P in order to find a proper hamiltonian path in G c . If this does not hold, we have that d(v) = n -1. Therefore the graph G c -{v} on n -1 vertices has at least

(n-1)(n-2) 2 + 1 -(n -1) ≥ (n-2)(n-3) 2
+ 1, then, again, we have a proper hamiltonian path P in G c . Now, if the path either starts or ends with a color different from red, we trivially add v to the path. If not, both of them finish with red. Now, if we can take any parallel edge of these without losing the property of being properly colored we have again that it is easy to add v to the path. Otherwise, we have, without losing generality, the degree in some color, say c 1 of the first vertex of the path, say w, is at most n -3. So, we are in the same case as the first one, since we take the graph G c -{v} and we delete from w the edges in that color c 1 and in another color in order to have w monochromatic not in red. By this, we delete n -1 + n -2 + n -3 = 3n -6 edges and finally, the result follows exactly as in the first situation.

Subcase B2: There exist two distinct edges incident to v, say vx and vy, such that c(vx) = c 1 = c 2 = c(vy). Assume first that x = y. This case is analog to the last one just taking the graph G c -{v} and deleting from w edges in the appropriate two colors in order to have it monochromatic. By this we delete 3 + 2(n -2) = 2n + 1 edges and we have that

(n-1)(n-2) 2 + 1 -(2n + 1) ≥ (n-2)(n-3) 2 + 1 for n ≥ 7.
Assume next that x = y. We will prove the result by induction. If we cannot attach v to the path P we have that there are 4 missing edges in colors different from red between v and the vertices x 1 , y p . Also, we have at most 2 edges different from red between v and the edges y i x i+1 of the path. Therefore there are 2 n-3 2 missing edges. Adding up all this, we conclude that the degree of v in colors different from red is at most n -3. So, if we replace the three vertices v, x, y to a new one, say v , such that

N c 1 (v ) = N c 1 G c -{v,x,y} (y), N c 2 (v ) = N c 2 G c -{v,x,y} (x) and N c 3 (v ) = N c 3 G c -{v,x,y} (x) ∩ N c 3 G c -{v,x,y} (y)
. So, by this we delete at most 5n -10 edges. Now, it is easy to see that the new 3-edge-colored multigraph on n -2 vertices, say G c , has at least (n-1)(n-2) 2 +1-(5n-10) ≥ (n-3)(n-4) 2 +1, for n ≥ 5, therefore, by inductive hypothesis, we have a proper hamiltonian path P in G c . Now, because of the way we have chosen the edges to delete at x and y, it is easy to obtain from P a proper hamiltonian path for G c .

Since we covered all the cases, the theorem is proved.

Theorem 5.3.2 is the best possible. Indeed, consider a rainbow complete graph on n-1 vertices with c colors and add a new isolated vertex x. The resulting graph, although it has c (n-1)(n-2) 2 edges, contains no proper hamiltonian path since it is not connected. Notice that in the above theorem there is no condition guaranteeing the connectivity of the underlying graph. Next result adds this condition. The proof is by induction on n. The cases n = 9, 10 can be shown by a tedious case analysis. We have two cases, depending on whether G c contains a monochromatic vertex or not.

Case a: There exists a monochromatic vertex in G c . Let x be a monochromatic vertex. Let y be a neighbor of x. If y is also monochromatic then the graph G c -{x, y} has n -2 vertices and at least 3(n-2)(n-3)

2 + n -(2n -3) = 3(n-2)(n-3) 2 -n + 3 edges, i.e.,
it is almost rainbow complete and therefore it has a proper hamiltonian cycle. Then, it is easy to add x and y to the cycle to obtain a proper hamiltonian path in G c . Suppose then that y is not monochromatic and that xy is of color b.

Let us replace the vertices x and y by a new vertex, say z, such that

N b (z) = N r (z) = ∅ and N g (z) = N g (y) (or N b (z) = N g (z) = ∅ and N r (z) = N r (y)).
Observe that, if the resulting multigraph on n -1 vertices is connected, (we show this later) and has enough edges for the induction hypothesis to hold, by induction it contains a proper hamiltonian path. Since z is monochromatic, it can only be the endpoint of the path. Therefore, using the blue edge xy, we can extend the path to a proper hamiltonian one in the initial multigraph.

We now count the maximum number of edges that may be deleted by the contraction. We delete all the edges incident to x, which is at most n -1, and the edges of color b and say g (or r) incident to y, at most 2(n -2). This gives us a total of 3n -5 edges. We now show that we can choose x and y for the contraction process, such that we delete at most 3 (n-2)(n-3) 2 + n -3 (n-3)(n-4)

2

n + 1 = 3n -8 edges, necessary for the induction hypothesis to hold.

We have the following cases, depending on d b (x). First of all, note that if d b (x) ≤ n-4, we delete at most n-4+2(n-2) = 3n-8 edges from x and any selected neighbor y of x and we are done. Further, from a theorem in [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], if

d i (z) ≥ n 2 ∀z ∈ V (G c -{x}); i ∈ {r, g, b}, then G c -
{x} has a proper hamiltonian cycle. This would imply a proper hamiltonian path in G. Thus, we may assume that there exists some vertex w ∈ G c -{x} such that d i (w) < n 2 for some i ∈ {r, g, b}. Case d b (x) = n -1. Observe that w ∈ N b (x). In this case, the contraction process deletes n -1 edges from x, and at most n -2 + n 2 -1 from w, much less than 3n -8 for n > 10.

Case d b (x) = n -2. Let w be the only vertex not adjacent to x. Now, if there is a vertex y adjacent to x such that d r,b G c -x (y) ≤ 2n -6 or d r,g G c -x (y) ≤ 2n -6. We choose x and y for the contraction process. Otherwise, for all y adjacent to x we have that d r,b G c -x (y) ≥ 2n -5 and d r,g G c -x (y) ≥ 2n -5. Therefore, by the theorem in [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], G c -{x, z} has a proper hamiltonian cycle. Now, since d b (x) = n -2 it is easy to add x and w to the cycle to form a proper hamiltonian path for G c . Case d b (x) = n -3. If there is a vertex y adjacent to x such that d r,b G c -x (y) ≤ 2n -5 or d r,g G c -x (y) ≤ 2n -5. We choose x and y for the contraction process. Otherwise, for all y adjacent to x we have that d r,b G c -x (y) ≥ 2n -4 and d r,g G c -x (y) ≥ 2n -4, i.e., the graph G cx is raibow complete and therefore, it has a proper hamiltonian cycle. Finally, we trivially add x to the cycle to form a proper hamiltonian path for G c .

Case b: There is no monochromatic vertex in G c . First suppose that there exists a vertex x such that |N (x)| = 1. Pick x and some vertex y ∈ N (x), for the contraction. We delete at most 3 edges at x and 2n -4 at y, which guarantees the induction hypothesis.

In what follows, we suppose that |N (x)| ≥ 2 for all x ∈ G c . We describe another contraction process, but now between 3 vertices. Consider a vertex x, y, z ∈ N (x) and suppose that c(xy) = b and c(xz) = r = c(xy). For the contraction, replace x, y and z by a new vertex say s, such that N r (s

) = N r G c -{x,y,z} (y), N b (s) = N b G c -{x,y,z} (z) and N g (s) = N g G c -{x,y,z} (y) ∩ N g G c -{x,y,z} (z)
. If the resulting multigraph has a proper hamiltonian path, it is easy to obtain a proper hamiltonian path for the initial graph since we chose the appropriate edges to delete at y and z. Let us count now the maximum number of edges that may be deleted in the contraction process.

We now need to select x, y and z so that we delete at most 3 (n-2)(n-3) 2 +n-(3 (n-4)(n-5) 2 + n -2) = 6n -19 edges, necessary for the induction hypothesis to hold.

Since we delete at most 3n -6 edges incident to y and z in G cx, if the degree of x is at most 6n -19 -(3n -6) = 3n -13, the hypothesis holds. If not, we show that there exist x,y and z such that the total number of deleted edges in the contraction process is less than or equal to 6n - [START_REF] Bondy | Graph theory with applications[END_REF].

In what follows we show how to find the desired triplet. We have two cases, depending on the parity of n.

Let E i be the set of edges in color i and suppose that the color b maximizes

|E i |. The monochromatic subgraph in color b has at least m b ≥ (n-2)(n-3) 2 + n
3 edges. We distinguish two possibilities. If this subgraph is connected, then by Lemma 5.1.5 there is a perfect matching for n even and almost perfect matching for n odd. Otherwise, there is a matching of size n-2 2 for n even and n-1

2 if n is odd. Let M b denote the maximum matching in E b .
• n is even. Let P = x 1 y 1 x 2 y 2 . . . x p y p be the longest proper path compatible with M b . It is easy to check that |P | ≥ 4, otherwise there are not enough edges in G c . Suppose now that there is a proper cycle C such that V (C) = V (P ). We have the following cases.

(1) |M b | = n 2 . By Lemma 5.1.4, we can check that |P | ≥ n -2, otherwise there is a contradiction with the total number of edges of the graph. Now, if |P | = n -2, we trivially add the edge of the matching outside the path since P also defines a proper cycle and the graph is connected. If |P | = n, P is a proper hamiltonian path and we are done.

(

) |M b | = n-2 2
2 . By Lemma 5.1.4, we can check that |P | ≥ n -4, otherwise, as before, there is a contradiction with the number of edges of the graph. Suppose first that |P | = n -4. Let xy be the edge of the matching outside P . Clearly, there are no edges in color g or r between xy and the cycle otherwise we would have a longest proper path compatible with the matching. Then, we have that d r,g (x) ≤ 6 and therefore d(x) ≤ 6 + n -1 < 3n -13. So we take x with any two neighbors in different colors for the contraction process and we are done. Suppose now that |P | = n -2. Let x, y be the unmatched vertices.

For every edge y i x i+1 on the cycle we can have at most 4 edges in colors r and g between their endpoints and the vertices x, y. Otherwise, we can add x and y to the cycle in order to obtain a proper hamiltonian path. Therefore, without losing of generality d r,g (x) ≤ 2 n-2 2 + 2. Same observation applies for the blue edges x i y i . This is, we can have at most 2 blue edges between their endpoints and the vertices x, y. Then

d b (x) ≤ n-2 2 -1. Summing up we have d(x) ≤ n + n-2
2 -1 < 3n -13. Thus, we can take x for the contraction process.

Let us suppose now that there is no proper cycle C such that V (C) = V (P ).

Consider the following cases as we did before.

(1) |M b | = n 2 . By Lemma 5.1.4 we can check that |P | ≥ n -4. If P is hamiltonian we are done. Otherwise, there is at least one edge in M b \ (P ∩ M b ). Clearly, there are no edges in color r and g from the extremities of P to the edges in M b \ (P ∩ M b ). Now, for each each edge outside the matching, there are at most 4 edges between their endpoints and the endpoints of the edges y i x i+1 , otherwise we can obtain a longer path. Therefore, taking the vertex, say x, outside P with minimum degree, we have that d r,g (x) ≤ 2 n-6 2 + 6, for |P | = n -4, and d r,g (x) ≤ 2 n-4 2 + 2, for |P | = n -2. In both cases, if we consider d b (x) = n -1, we get d(x) ≤ 3n -13 and we take it for the contraction.

(

) |M b | = n-2 2 . 2
For |P | = n -4 the proof is similar as previous case. Suppose then that |P | = n -2. Let v, w be the unmatched vertices. We try to add these vertices to the path either at the extremities or between vertices y i , x i+1 . Suppose first that we cannot add any of them. Then d r,g (v) ≤ 2 n-4 2 + 2. Summing up this with at most n-2 blue edges we obtain d(v) ≤ 2n-4 < 3n-13 and we take v for the contraction. Suppose last that we can add v but we cannot add w. If v was added at one extremity of the path we obtain that

d(w) ≤ 2 n-4 2 + 1 + n -2 = 2n -5 < 3n -11. If v was added between the path, we have d(w) ≤ 2 n-6 2 + 2 + n -2 = 2n -6 < 3n -11.
In both cases we can take w for the contraction.

• n is odd and therefore |M b | ≥ n-1 2 . Let P = x 1 y 1 x 2 y 2 . . . x p y p be the longest proper path compatible with M b . It is easy to check that |P | ≥ 4, otherwise there are not enough edges in G c . Then we distinguish two cases:

(1) There is a proper cycle C such that V (C) = V (P ). By Lemma 5.1.4 we can check that |P | ≥ n -5. If |P | = n -1 we are done since is trivial to add the unmatched vertex to the cycle to obtain a proper hamiltonian path. If n -5 ≤ |P | ≤ n -3, as in the even case, we can use for the contraction any vertex incident to any edge of the matching outside the path, since there are no red and green edges at all between the edges of the matching outside the path and the path.

(2) There is no proper cycle C such that V (C) = V (P ). Again, by Lemma 5.1.4 we can check that |P | ≥ n -5. This case is also similar to the even case.

For n -5 ≤ |P | ≤ n -3, we try to extend P with the edges of the matching outside the path. Since this is not possible we can chose one matched vertex outside the path to do the contraction. For |P | = n -1, we try to extend P with the unique unmatched vertex. If this is not possible, we can use it for the contraction and we are done.

Since we cover all cases, we can always find three appropriate vertices to make the contraction process. We now check the connectivity of the resulting multigraph after the contraction of 2 and of 3 vertices.

• We contract two vertices x, y, where x is monochromatic and y is a neighbor of x, to a vertex s. Suppose that the graph is disconnected. It can be easily shown that the graph has two components with 1 vertex and n -2 vertices respectively. Otherwise, there is a contradiction on the total number of edges of the graph. Observe first that the isolated vertex cannot be s unless the x and y are both monochromatic, but this case was solved independently. Then, as we have the choice at y of which colors to delete, s cannot be isolated and therefore this case cannot occur. Suppose now that a vertex z is the isolated vertex. Now, as we delete at most 3n -8 edges for the contraction process, we have at least 3n -1 edges in E(G c ). Then, since the graph is disconnected, there are no edges between both components and therefore 3n -9 more edges in E(G c ). Summing up we obtain 6n -10 edges in E(G c ). A contradiction.

• We contract three vertices x, y, z to a vertex s. Suppose that the graph is disconnected. Again, this graph has exactly two components with 1 vertex and n -3 vertices respectively. If the isolated vertex z is not s we have 3n -12 edges in E(G c ) since there are no edges between both components. Now, in the contraction process we deleted at most 6n -19 edges, therefore there are 3n + 1 more edges in in E(G c ). Again, if we sum up we obtain 6n -11 edges in E(G c ). Another contradiction.

+ n that has a proper hamiltonian path. We will do this reduction by contracting 2 or 3 vertices depending on if there exists a vertex x in G c , such that |N r,g,b (x)| = 1 or not.

• There exists a vertex x ∈ G c such that |N r,g,b (x)| = 1. Let y be the neighbor of x. We replace x and y by a new vertex s, such that N r (s) = N r (y) and N b (s) = N g (s) = ∅. Clearly, we delete 3 edges between x and y and at most 2(n -2) edges in color b and g incident to y. This gives us a total of 2n -1 deleted edges. For the reduction hypothesis we can delete at most

3(n-2)(n-3) 2 + 7 -3(n-3)(n-4) 2 -n + 1 = 2n -1 edges.
Observe that the resulting multigraph on n -1 vertices is connected since as rd(x) = 3, we can choose at y which two colors to delete, therefore since the original graph is connected it is impossible that in all 3 possible choices the graph after contraction would be disconnected. So, as we deleted 2n -1 edges and the graph is connected, by Theorem 5.3.3, it has a proper hamiltonian path. Now, since s is monochromatic, it can only be the endpoint of the path. We can replace back s with x and y using the edge xy in color b and find the proper hamiltonian path for the initial multigraph.

• There is no vertex x ∈ G c , such that |N r,g,b (x)| = 1. Let us suppose that there are 3 vertices x, y and z, such that xy is in color b, and xz in color r. Then, we replace x, y and z by a new vertex s, such that N r (s

) = N r G c -{x,y,z} (y), N b (s) = N b G c -{x,y,z} (z) and N g (s) = N g G c -{x,y,z} (y) ∩ N g G c -{x,y,z} (z)
. Clearly, we delete at most 3(n -1) edges incident to x, n -3 edges in b incident to y, n -3 edges in r incident to z, n -3 in color g incident to y and z, and 3 edges between y and z. In total we delete at most 6n -9 edges. Only 3(n-2)(n-3) 2 + 7 -3(n-4)(n-5)

2

n + 2 = 5n -12 edges can be deleted to make the reduction. Therefore, we need to find a vertex x such that its total degree is less than or equal to 2n -6. 2 for n odd. Let P = x 1 y 1 x 2 y 2 . . . x i y i . . . x p y p be the longest proper path compatible with M b . The proof is divided in two cases depending on the parity of n.

Suppose without losing generality that |E

b | ≥ |E r | ≥ |E g |, then |E b | ≥ 3(n-2)(n-3)
(1) n is even.

-There is a proper cycle C such that V (C) = V (P ). By Lemma 5.1.4 we can check that |P | ≥ n -2, otherwise we have a contradiction with the number of edges. This case is trivial since, either P is a proper hamiltonian path or we can add the unique edge of the matching outside P directly to the cycle to obtain a proper hamiltonian path since the graph is connected.

-There is no proper cycle C such that V (C) = V (P ). By Lemma 5.1.4 we can check that |P | ≥ n -4. Let x be the vertex in M b \ (M b ∩ P ) with minimum degree. Clearly, there cannot be edges in colors r and g between M b \ (M b ∩ P ) and the extremities of P . Also, there can be at most 4 edges in colors r and g from each edge in M b \ (M b ∩ P ) and the edges y i-1 x i in P . Then, we can conclude that there are at most 2 2p-2 2 edges in color r and g, between x and the vertices in P . Suppose now that there is one parallel edge in color r or g between the blue edge of the matching xy, then using edges xx i , yy i or yx i , xy i in color b, we can add the edge xy in color r or g into P . Since this contradicts our hypothesis we can conclude that there are 2 missing edges in color b from xy to each edge x i y i in P . Now, since there are 2p 2 edges x i y i we conclude that the vertex x has d b (x) ≤ 2p 2 + (n -2p -1). In total we have that d(x) ≤ 3(n -2p -1) + 2p 2 + (2p -2) = 3n -3p -5, and for |P | = n -2, this is less than or equal to 2n -6 and we can make the contraction with x. If |P | = n -4 there are 6n -20 missing edges in colors r and g. Suppose now that there are no edges in colors r and g between x and y, and the other edge of the matching outside the path. We obtain then, 4 missing edges more in colors r and g and therefore 6n -16.

Observe now that if we can replace the edges xy and the other edge of the matching outside P , say uv, in M b by xu and yv, then there are missing the 4 parallel edges in color r and g, obtaining 6n -12. A contradiction. Otherwise if not, there are 2 more missing edges and we obtain 6n -14. Again a contradiction. Finally, if |P | = n -2 and there are no parallel edges in r and g at xy, we have that d(x) ≤ 2n -5 and d(y) ≤ 2n -5. We can use one of these vertices unless both inequalities become equalities. In this case we try to replace the edges x i y i in P by x i xy i and x j yy j , i = j. Suppose that we have the edges xx i in colors r and g, xy i in color b, yx j in colors r and g, and yy j in color b. Then we have a proper hamiltonian path P = x 1 y 1 . . . x i xy i x i+1 . . . x j yy j . . . x p y p . Otherwise at least one of those edges is missing and therefore either d(x) ≤ 2n -6 or d(y) ≤ 2n -6 as desired.

(2) n is odd.

-There is a proper cycle C such that V (C) = V (P ). By Lemma 5. -There is no proper cycle C such that V (C) = V (P ). By Lemma 5.1.4 we can check that |P | ≥ n-7. Suppose first |P | < n-1. Let xy and uv be two edges in M b \ (M b ∩ P ) where x has the minimum degree. There cannot be edges in colors r and g to the extremities of P and there can be only 4 edges in colors r and g between M b \(M b ∩P ) and y i-1 x i in P . Suppose now that there exists an edge xy in color r or g, then we can use the edges in color b between xy and x i y i to extend P . Since it is not possible we conclude that there are only 2p 2 + (n -2p -1) edges in color b at x. For |P | = n -7

or y, unless both inequalities become equalities. Now, if we suppose that c(xz) = r, we contract the three vertices x, y and z such that we delete at most 2n -5 edges at x, n -3 blue edges at y, n -3 red edges at z, n -3 green edges with common enpoints at y and z and 2 edges, one red and one green between y and z. We remark that the blue edge yz is not present. By this, we delete at most 5n -12 edges, i.e., the required number for the contraction.

Finally, suppose that |P | = n -1. Let z be the unmatched vertex. Then, for same reasons as before, d r,g (z) ≤ n -3. If we suppose that there are edges in color r and g between z and y i , then there cannot be the edges x i z in color b, otherwise a hamiltonian path can be found. Suppose there are no such edges then, by Lemma 5.1.3, either x 1 or y p have degree in colors r and g at most n -3. If there is at least one of the edges zy 1 or zx p in color b, then we can replace z by either x 1 or y p . In both cases, we arrive that d(x 1 ) ≤ 2n -6 or d(y p ) ≤ 2n -6, otherwise d(z) ≤ 2n -6 and the contraction can be done.

Since all cases were covered, there always exists a vertex x such that d r,g,b (x) ≤ 2n -6 and the contraction can be done. Therefore by Theorem 5.3.3 we obtain a proper hamiltonian path in this new graph. Then, it is simple to extend this path to a proper hamiltonian one in the initial graph because of the choice of the edges to delete at the contracted vertices.

We will check now the connectivity of the resulting multigraph after the contraction of 3 vertices. Suppose we contract three vertices x, y, z to a vertex s. Suppose that the graph is disconnected. This graph has exactly two components with 1 vertex and n -3 vertices respectively. If the isolated vertex z is not s we have 3n-12 edges in E(G c ) since there are no edges between both components. Now, in the contraction process we deleted at most 5n -12 edges, therefore there are 4n -6 more edges in in E(G c ). Summing up we obtain 7n -18 edges in E(G c ). A contradiction. Suppose finally that z = s. As we deleted at most 5n-12 edges, the new graph has at least 3(n-2)(n-3) 2 +7-5n+12 = 3(n-4)(n-5) 2 +n-2 edges in the component of n -3 vertices. As in the previous theorem, this component has a proper hamiltonian cycle (Theorem 6.2.2) and therefore, it is trivial to add the three contracted vertex to obtain a proper hamiltonian path for the initial graph. Now as the connectivity is proved the theorem holds.

Chapter 6

Proper Hamiltonian Cycles in Edge-Colored Multigraphs

As in Chapter 5, we divide this chapter in two sections. In Section 6.1 we study proper hamiltonian cycles in 2-edge-colored multigraphs and in Section 6.2 we study proper hamiltonian cycles in c-edge-colored multigraphs, for c ≥ 3. Again, this division is because, since proper cycles in 2-edge-colored multigraphs are just alternating, proper hamiltonian cycles only can exist if n is even (condition not required when c ≥ 3).

2-edge-colored multigraphs

In this section we study the existence of proper hamiltonian cycles in 2-edge-colored multigraphs. We present two main results. The first one involes the number of edges and the second one, the rainbow degree and the number of edges. Both results are tight. Lemma below is established in view of Theorem 6. Proof. Let red and blue be the two colors of G c . The proof is by induction on n. The theorem is true for small values of n, say n = 2, 3, 4. Let us suppose that n ≥ 5 and that the theorem is true until n -1. We will prove it for n. By a Theorem of [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], if for every vertex x we have that d r (x) ≥ n+1

(x) = 0, then m ≤ n(n -1) -(n -1) = (n -1) 2 < (n -1)(n -2) + n, a contradiction. Similarly d r (x) + d b (x) ≥ 3, otherwise, if d r (x) + d b (x) ≤ 2, then m ≤ n(n -1) -2n + 4 = n 2 -3n + 4 < (n -1)(n -2) + n,
(n -1) -(n -3) -(n -3) = n 2 -3n + 6 < (n -1)(n -2)
+ n, again a contradiction. This completes the argument and the proof. Theorem 6.1.2 is the best possible for n ≥ 4. Consider a rainbow complete 2-edgecolored multigraph on n -1 vertices (n even). Add one new vertex x. Then add all possible edges in one color, say red, between x and the complete graph. Clearly, the resulting graph has m ≥ (n -1)(n -2) + n -1 edges and it has no proper hamiltonian cycle since x has just color red incident to it.

• x = u and x = w. Suppose first that d r (x) = 2 then, x is adjacent to v and w in red.

In this case, we proceed exactly as in the first case, adding the red edge vx to the proper hamiltonian cycle (or proper cycle of length n -3) that exists in G c -{v, x}. Suppose now d b (x) = 2 then, x is adjacent to v and u in blue. Here, we repeat the argument as in the second case, adding the blue edge vx to the proper hamiltonian cycle (or proper cycle of length n -3) that exists in G c -{v, x}, choosing again the cycle that contains the second vertex z such that z is adjacent to v in red.

The last case that we have to consider is when in the new graph G c every vertex x has rd(x) = 2. We can see that this graph has at least (n -2)(n

-3) + 2(n -2) + 4 -(n - 1) -( n+1 2 -1) -(n -3) -(n -3) -2 edges.
This number, for n ≥ 11, is greater or equal than (n -4)(n -5) + 2(n -4) + 4, i.e., the number of edges needed to have a proper hamiltonian cycle or a proper cycle of length n -3 (n odd) in G c . So by the inductive hypothesis we obtain such a cycle. For n even, it is easy to obtain a proper hamiltonian cycle for G c , since we deleted the appropriate edges at u and w. For n odd, if the new vertex z is on the cycle of length n -3, it is exactly the same as for the even case to obtain a proper cycle of length n -1 for G c . Now, if the vertex z is not on the proper cycle, let x 1 y 1 x 2 y 2 . . . x k y k x 1 with 2k = n -3 be the proper cycle. Suppose without losing generality that the edges x i y i are red and the edges y i x i+1 are blue. If we cannot add neither the blue edge vu nor the red edge vw to the cycle, then we have at most 2 red edges between the endpoints of the edge vu and the endpoints of the edges x i y i and at most 2 blue edges between the endpoints of the edge vw and the endpoints of the edges y i x i+1 . So, since the length of the cycle is n -3, there are n-3 2 + n-3 2 = 2n -6 edges is E(G c ). Therefore, we have all possible edges in G c but those missing ones. In particular we have the red edge uv and the red edge uw. Now, if there is a blue edge from v to some vertex x i (y i ) of the cycle, we extend the proper cycle to a proper cycle of length n -1 with the red edge uv adding the blue edge vx i (vy i ), the blue edge uy i-1 (ux i+1 ) and removing the blue edge x i y i-1 (y i x i+1 ) from the cycle. The blue edge uy i-1 (ux i+1 ) clearly exists since u has all possible blue incident edges. If there is no blue edge from v to some vertex x i (y i ) of the cycle, we have that there exists a blue edge from w to some vertex x i (y i ) of the cycle. Otherwise, we have that d b (v) = 2 and d b (w) = 2, and we have covered that case before. Finally, we extend the proper cycle to a proper one of length n -1 exactly as we did to add the red edge uv but now with the red edge uw.

The proof is now complete. Theorem 6.1.3 is the best possible for n ≥ 9. Indeed, for n even, consider a complete blue graph, say A, on n -2 vertices. Add 2 new vertices v 1 , v 2 and join them to a vertex v in A with blue edges. Finally, superpose the obtained graph with a complete red graph on n vertices. Although the resulting 2-edge-colored multigraph has (n-2)(n-3)+2(n-2)+3 edges, it has no proper hamiltonian cycle since there is not a perfect blue matching because v 1 and v 2 are only adjacent in blue to v. We remark that for n = 8, the graph H 2 k,k+2 , k = 3, has (n -2)(n -3) + 2(n -2) + 4 edges but no proper hamiltonian cycle.

c-edge-colored multigraphs, c ≥ 3

In this section we study the existence of proper hamiltonian cycles in 3-edge-colored multigraphs. We present two main results. The first one involes the number of edges and the second one, the rainbow degree and the number of edges. Both results are tight. Finally, we state a conjecture involving the rainbow degree, the number of edges and the connectivity.

First, we will present a similar result to that for proper hamiltonian paths, that allows us to consider just the case c = 3. We omit the proof since is exactly the same as for paths. Lemma 6.2.1. Let G c be a c-edge-colored connected multigraph on n vertices, c ≥ 4 and m ≥ c f (n) + 1 edges. There exists one color c j such that if we color its edges with another used color and we delete parallel edges with the same color, then the resulting (c -1)-edge-colored multigraph is connected and has m ≥ (c -1) f (n) + 1 edges, such that if G c-1 has a proper hamiltonian cycle then G c has one too. Moreover, if rd(G c ) = k, then rd(G c-1 ) = k -1 for 1 ≤ k ≤ c. Theorem 6.2.2. Let G c be a c-edge-colored multigraph on n vertices, n ≥ 4 and c ≥ 3.

If m ≥ c(n-1)(n-2)

2

+ n, then G c has a proper hamiltonian cycle.

Proof. By Lemma 6.2.1 it is enough to prove the theorem for c = 3. So we have that m ≥ 3(n-1)(n-2) 2 + n. We prove the theorem by induction on n. For n = 4 the theorem is easily checked. Suppose then that n ≥ 5. We take two vertices v and w such that they are adjacent in all colors r, b and g. It can be checked that two vertices like these always exists otherwise, if every pair of vertices have at most two edges between, the number of edges would be less than the hypothesis.

Observe first that d(v), d(w) ≤ 3n -5. Otherwise, if d(v) ≥ 3n -4 we can remove v from G 3 obtaining a graph with number of edges at least 3(n-1)(n-2) 2

+ n -3(n -1) = 3(n-2)(n-3) 2 + n -3 ≥ 3(n-2)(n-3)
2 + 1 and therefore by Theorem 5.3.2 we have a proper hamiltonian path in G 3v. Then, since d(v) ≥ 3n -4 we can easily connect v to the endpoints of the path in an appropriate way in order to obtain a proper hamiltonian cycle. So, we can assume that d(v), d(w) ≤ 3n -5. Now we will contract v and w to a single vertex to apply the inductive hypothesis in this new graph on n -1 vertices. For that, we have to show that this graph has at least 3(n-2)(n-3) 2

+ n -1. For this we can check that the difference between these two functions is 3n -5 edges, that is, the maximum number of edges that we are allowed to delete in the contraction process. So, suppose that we contract v, w to a new vertex z such that

N r (z) = N r (v) -w, N b (z) = N b (w) -v and N g (z) = N g (v) ∩ N g (w)
. Like this, since d(v), d(w) ≤ 3n -5 we delete at most 3n -5 edges as desired.

Finally, it is easy to see, once we obtain a proper hamiltonian cycle in the contracted graph, how to obtain a proper hamiltonian cycle in the original graph. Theorem 6.2.2 is the best possible for n ≥ 4. Consider a rainbow complete c-edgecolored multigraph on n -1 vertices. Add one new vertex x. Then add all possible edges in one color, say red, between x and the complete graph. Clearly, the resulting graph has m ≥ c(n-1)(n-2)

2

+ n -1 edges and it has no proper hamiltonian cycle since x has just color red incident to it. Proof. By Lemma 6.2.1 it is enough to prove the theorem for c = 3. So we have that m ≥ 3(n-1)(n-2) 2 + 4 and for every vertex x of G 3 , rd(x) = 3. We prove the theorem by induction on n. For n = 4, 5 the theorem is easily checked. Suppose then that n ≥ 7. We take two vertices v and w such that they are adjacent in all colors r, b and g. It can be checked that two vertices like these always exists otherwise, if every pair of vertices have at most two edges between, the number of edges would be less than the hypothesis.

Observe first that d(v), d(w) ≤ 3n -5. Otherwise, if d(v) ≥ 3n -4 we can remove v from G 3 obtaining a graph with at least 3(n-1)(n-2) 2 + 4 -3(n -1) = 3(n-2)(n-3) 2 + 1 edges. This is exactly the number of edges needed by Theorem 5.3.2 to have a proper hamiltonian path in G 3v. Therefore, since d(v) ≥ 3n -4 we can easily connect v to the endpoints of the path in an appropriate way in order to obtain a proper hamiltonian cycle. So, we can assume that d(v), d(w) ≤ 3n -5. Now we will contract v and w to a single vertex to apply the inductive hypothesis in this new graph on n -1 vertices. For that, we have to show that this graph has at least 3(n-2)(n-3) 2

+ 4 edges and for every vertex x, rd(x) = 3. For this we can check that the difference between these two functions is 3n -6 edges, that is, the maximum number of edges that we are allowed to delete in the contraction process. So, suppose that we contract v, w to a new vertex z in a trivial way such that

N r (z) = N r (v) -w, N b (z) = N b (w) -v and N g (z) = N g (v) ∩ N g (w)
. Like this, since d(v), d(w) ≤ 3n -5 we delete at most 3n -5 edges. So we need to delete one edge less to apply the inductive hyphotesis. Clearly, if either d(v) ≤ 3n -6 or d(w) ≤ 3n -6, we can choose the colors to delete in order to remove 3n -6 edges as desired. Suppose then that d(v) = d(w) = 3n -5. Remove now v from the graph. As before we have a proper hamiltonian path P = v 1 v 2 . . . v n-1 in G 3v where w = v i for some i. Now we extend this path with v to a proper hamiltonian cycle. If we cannot trivially extend it adding v properly to the endpoints, we have that v (without losing generality) has the three colors to v 1 and just one color to v n-1 where this color is the same as in the edge v n-2 v n-1 in P (say r). Therefore since d(v) = 3n -5, v is fully connected to all vertices but v n-1 . We can suppose that w = v 1 , otherwise it is easy to see how to extend P with v to a cycle using the fact that d(w) = 3n -5. Now, suppose that v n-1 has an edge to w = v i with color b (similar with g). If wv i+1 is b we have the proper hamiltonian cycle v n-1 wv i-1 . . . v 1 vv i+1 . . . v n-1 . Otherwise, if v i-1 w is b we have the following one: v n-1 wv 1 . . . v i-1 vv i+1 . . . v n-1 . We can conclude that w is adjacent to v n-1 only in r and fully connected to the other vertices. Finally, since rd(v n-1 ) = 3, there exists a vertex v j adjacent to v n-1 with some color different than r. As we have just done, we can always find a proper hamiltonian cycle in this situation considering different cases when j < i and i < j. Finally, either d(v) ≤ 3n -6 or d(w) ≤ 3n -6. So we can therefore contract v, w to a vertex z removing at most 3n -6 in order to obtain a graph on n -1 with at least 3(n-2)(n-3) 2 + 4. The problem now is that in this new graph, the rainbow degree condition may be not respected anymore since we can have vertices (at most 2) with just one color incident to them. Suppose then, that there exists a vertex x ∈ G 3 and a color, say r, such that d r (x) = 1. We show this case independently on the rest of the proof. Let z be the only neighbor of x with color r and let y = z be another neighbor of x in another color, say b. Clearly y must exist otherwise the number of edges on the graph would be less than the hypothesis. Now we contract the vertices x, y and z to a new vertex w in order to apply Theorem 6.2.2 to a graph on n -2 vertices. For this, we can check that we can delete at most 5n -9 edges. If we contract them in a trivial way such that N r (w

) = N r G 3 -{x,y,z} (y), N b (w) = N b G 3 -{x,y,z} (z)
and N g (w) = N g G 3 -{x,y,z} (z) ∩ N g G 3 -{x,y,z} (y) we remove at most 5n -7 edges, so we need to delete two edges less to apply Theorem 6.2.2. Observe that if we do not have colors b and g between x and z we obtain these two edges and therefore we remove 5n -9 edges as desired. So, we have at least two colors between x and z, r and, say b. Now consider the graph G 3 -{x, z}. We can check that by Theorem 5.3.2, the graph has a proper hamiltonian path P = v 1 v 2 . . . v n-2 . We can suppose also that y = v 1 (or y = v n-2 ), since otherwise if x is not adjacent to any of v 1 , v n-2 in colors b or g we find the two edges less to delete for the contraction. We have the following cases now. Suppose first that there are exactly colors r and b between x and z. So, we need to find one more edge in order to arrive to 5n -9. Therefore, x should be adjacent to both y = v 1 and v n-2 in colors b and g, otherwise we obtain the last edge to get 5n -9. Now, if z is adjacent to v 1 in both colors b and g, we easily obtain a proper hamiltonian cycle otherwise we obtain the edge less to delete. Suppose last that there are the three colors r, b and g between x and z. Therefore, x should be adjacent without losing generality to v 1 in at least color b and to v n-2 in colors b and g, otherwise we obtain two edges less to get 5n -9. If x is adjacent to v 1 just in color b, as before, if z is adjacent to v 1 in both colors b and g we are done since either we have a proper hamiltonian cycle or we obtain the 5n -9 edges. If x is adjacent to v 1 in colors b and g, depending on the color of v 1 v 2 , if z is adjacent to v 1 in two colors we obtain again a proper hamiltonian cycle. Otherwise, two edges are missing between z and v 1 . As we covered all cases, we can then contract x, y and z as we described above.

Finally, it is easy to see once we obtain a proper hamiltonian cycle in the contracted graph (when we contract 2 or 3 vertices) how to obtain a proper hamiltonian cycle in the whole graph. Theorem 6.2.3 is the best possible for n ≥ 4. Consider a rainbow complete c-edgecolored multigraph on n -1 vertices. Add one new vertex x. Then, add all possible edges in all colors between x and one vertex of the complete graph. Clearly, the resulting graph has m ≥ c(n-1)(n-2) 2 + c edges, every vertex has rainbow degree c but it has no proper hamiltonian cycle since it is not 2-connected.

Finally, we state a conjecture for the existence of proper hamiltonian cycles involving not also the rainbow degree and the number of edges, but also the connectivity. If true, Conjecture 6.2.4 is the best possible for n ≥ 10. For this, consider a rainbow complete c-edge-colored multigraph on n -2 vertices. Add two new vertices x 1 and x 2 . Consider two vertices of the complete graph y 1 and y 2 . Finally, add all possible edges in all colors between x 1 and y 1 , x 1 and y 2 , x 2 and y 1 , and x 2 and y 2 . The resulting graph has m ≥ c(n-2)(n-3) 2 + 4c edges, it is 2-connected and every vertex has rainbow degree c. However, this graph has no proper hamiltonian cycle since one of the vertices x 1 or x 2 cannot be together in a proper hamiltonian cycle. If n = 7, 9, the graphs H c k,k+1 , k = 3, 4, are exceptions for Conjecture 6.2.4.

Next result remarks that we can delete false-twin vertices of the graph, since if two vertices are false-twins, they belong exactly to the same bicliques. Therefore, the deletion of one of them does not change neither the number of the bicliques of the graph nor the structure of its biclique graph. Notice that, differently than the clique operator, a graph is never periodic under the biclique operator (with period bigger than 1). We remark the importance of the graph K 5 to decide the behavior of a graph under the biclique operator, since we have that KB(gem) = K 5 and K 5 ⊆ KB(house).

As a corollary of Theorem 7.1.4 the next useful result was obtained. Note that if some vertex lies in five bicliques, then KB(G) contains a K 5 and then G diverges. Therefore, Corollary 7.1.5 gives a polynomial time algorithm to test convergence of G: if some vertex lies in five bicliques, answer that G is divergent. Else, the computation of KB(G) and T w(KB(G)) is polynomial (we remark however, that the number of bicliques of a graph can be exponential [START_REF] Prisner | Bicliques in graphs i: Bounds on their number[END_REF]). If T w(KB(G)) has at most four vertices, answer that G is convergent, otherwise, answer that G is divergent.

Constructing KB(G) takes O(n 4 ) time, since for the case that is done, the input graph G has at most 2n bicliques and generating each biclique is O(n 3 ) [START_REF] Dias | Generating bicliques of a graph in lexicographic order[END_REF][START_REF] Dias | On the generation of bicliques of a graph[END_REF]. To build T w(KB(G)) can be done in O(n 2 ) time. Therefore, the algorithm runs in O(n 4 ) time.

Linear time algorithm

In this section we give a linear time algorithm for deciding whether a given graph is divergent or convergent under the biclique operator.

Motivated by Theorem 7.1.4 and Corollary 7.1.5, we study the structure of biclique graphs with false-twin vertices, in order to find conditions to have K 5 as a subgraph that will guarantee the divergence of the graph.

We obtain the following two lemmas. Then for all x ∈ B 1 , x is adjacent to w. Suppose now that there is no vertex z in B 2 adjacent to w. Then there is a P 3 starting at v that is contained in a biclique B, B = B 1 and B = B 2 , that does not intersect B 2 leading to a contradiction. Then, let z ∈ B 2 be a vertex adjacent to w. Now, the same argument as in case v ∈ B 1 holds for z ∈ B 2 . Then for all z ∈ B 2 , z is adjacent to w.

Finally, let v, v be adjacent vertices in B 1 and let z, z be adjacent vertices in B 2 . Since v, v , z, z are adjacent to w, then {v, w, z}, {v , w, z}, {v, w, z } and {v , w, z } are contained in four bicliques B 3 , B 4 , B 5 and B 6 such that of G and let B 1 , B 2 , B 3 be their associated bicliques in H. Suppose that for any pair of bicliques B i , B j , 1 ≤ i = j ≤ 3, there is an edge between some vertex of B i and some vertex of B j . Then, K 5 is an induced subgraph of G.

B i = B j , for 1 ≤ i = j ≤ 6. So, as B i ∩ B j = ∅, for 1 ≤ i = j ≤ 5, K 5 is an induced subgraph of G.
Proof. Let b 1 , b 2 , b 3 be the false-twin vertices of G and B 1 , B 2 , B 3 their associated bicliques in H such that for any pair of bicliques B i , B j , 1 ≤ i = j ≤ 3, there is an edge between some vertex of B i and some vertex of B j . We have the following cases:

Case 1: There is a K 3 with one vertex in each biclique. . Now, w is only adjacent to w. As B 1 is a biclique there exists a vertex x ∈ B 1 adjacent to x such that does not extend the C 4 . As we saw before, x can be only adjacent to v and w . In each one of the cases we have that the sets {u, x, v, w}, {v, v , w, u}, {w, w , x, v} and {x, x , w, u} are contained in four different bicliques and they are mutually intersecting, and therefore K 5 is a subgraph of G.

We covered all the cases when a C 4 is in H with all of the vertices in the bicliques B 1 , B 2 and B 3 . Now we have the last case.

Case 3: There is an induced C k , k ≥ 5 in H with vertice in the bicliques B 1 , B 2 and B 3 . This case is easy since C k has k bicliques an each of them has to intersect the three bicliques B 1 , B 2 and B 3 . So K 5 is a subgraph of G.

Since we covered all cases the proof is done.

Next, we present the main theorem of this section. This theorem shows that almost every graph is divergent under the biclique operator. Also, it helps us two obtain the result that will imply the linear time algorithm. Consider the following cases.

Case n = 1. Then KB(G) = K 1 is a contradiction since G has at least 7 bicliques.

Case n = 2. Then KB(G) = K 2 or KB(G) is bipartite with more than two vertices.

In the first case, G has only 2 bicliques and therefore a contradiction. If KB(G) is bipartite with more than two vertices KB(G) is not a biclique graph [START_REF] Groshaus | Biclique graphs and biclique matrices[END_REF] and that leads to a contradiction.

Case n = 3. Since G has at least 7 bicliques, it follows that in KB(G) there exists a set of false-twin vertices of size at least three. Consider the bicliques B 1 , B 2 , B 3 of G associated to the three false-twin vertices. If there is a pair of bicliques B i , B j such that there is no edge between any vertex of B i and any vertex of B j , by Lemma 7.2.1, it follows that K 5 is an induced subgraph of KB(G). Otherwise, for every two pair of bicliques B i , B j there is an edge between some vertex of B i and some vertex of B j and by Lemma 7.2.2, KB(G) contains K 5 as an induced subgraph. In any case, by Theorem 7.1.4, G diverges under the biclique operator, a contradiction.

Case n = 4. There are two alternatives. Suppose that KB(G) has a set of false-twin vertices of size at least three. Then, following the proof of the case n = 3, we arrive to a contradiction. Otherwise, there are only two possible graphs isomorphic to KB(G) (KB(G) has 7 or 8 vertices, and it has no set of three false-twin vertices). By inspection, using the characterization given in [START_REF] Groshaus | Biclique graphs and biclique matrices[END_REF], we prove that these two graphs are not biclique graphs. We conclude that this case can not occur.

Since we covered all cases, G diverges under the biclique operator and the proof is finished.

Based on last theorem and in the fact that KB(G) = KB(T w(G)), it is interesting to know when a graph without false-twin vertices has at least 7 bicliques. Next theorem answers this question and, moreover, it gives us the linear time algorithm for the recognition of divergent and convergent graphs under the biclique operator. Proof. We prove the result by induction on n. For n = 13, by inspection of all graphs without false-twin vertices, the result holds. Suppose now that n ≥ 14. By a Theorem in [START_REF] Charon | Structural properties of twin-free graphs[END_REF], there is a vertex v such that Gv has no false-twin vertices. Consider the graph G = Gv. If G is connected, since it has at least 13 vertices, by inductive hypothesis, it has at least 7 bicliques. Now, as G is an induced subgraph of G, we conclude that G also has at least 7 bicliques. Suppose now that G is not connected. Let G 1 , G 2 , . . . , G s be the connected components of G on n 1 , n 2 , . . . , n s vertices respectively. Since G has no falsetwin vertices, it can be at most one G i such that n i = 1. If there is one component with at least 13 vertices, then by inductive hypothesis, this component has at least 7 bicliques and so does G. So, every component has at most 12 vertices. Now, by inspection we can verify that every component G i (but maybe one with just 1 vertex) has at least n i 2 bicliques. Also, since G is disconnected, v along with at least one vertex of each of the s components is a biclique in G isomorphic to K 1.r that is lost in G . Summing up and assuming the worst case, this is, there exists one n i = 1 (suppose i = s) we obtain that the number of bicliques of G is at least

Bicliques in false-twin free graphs

To finish this chapter and motivated by the fact that the amount of bicliques in graphs without false-twin vertices is lower bounded, we will study this class of graphs more extensively.

We start with the case when the graph is also K 3 -free. Based on last lemma, we obtain this immediat result. Now, we obtain the following important result that will help us to prove the main theorem of the section. Proof. Let v 1 , v 2 , . . . , v k be the neighbors of v. Clearly they are an independent set. Let x 1 , x 2 , . . . , x be the set of vertices adjacent to the vertices v 1 , v 2 , . . . , v k . Let G be the subgraph induced by {v} ∪ {v 1 , v 2 , . . . , v k } ∪ {x 1 , x 2 , . . . , x }. It is easy to see that v 1 , v 2 , . . . , v k are not false-twins in G and since G is K 3 -free, v is not adjacent to any x j , 1 ≤ j ≤ . Now, for each 1 ≤ i ≤ k, let S v i = {N G (x j ) : v i ∈ N G (x j ), 1 ≤ j ≤ } ∪ N (v). Let Cl(S v i ) = S∈Sv i S. Observe first that S v i = ∅ for all i since N (v) belongs to all of them. Observe then that Cl(S v i ) ∪ ({x j : N G (x j ) ∈ S v i , 1 ≤ j ≤ } ∪ {v}) is a biclique in G and therefore a biclique in G. We show now that, for all i = j we have that Cl(S v i ) = Cl(S v j ), i.e., v belongs to k different bicliques in G. Suppose by contrary, that Cl(S v i ) = Cl(S v j ). Now, since v i ∈ Cl(S v i ), we have that v i ∈ Cl(S v j ). Similarly, v j ∈ Cl(S v i ). So, for all S ∈ S v i , we have that v j ∈ S. Also, for all S ∈ S v j , we have that v i ∈ S. This is N (v i ) = N (v j ), a contradiction since G has no false-twin vertices. Now, the result follows.

As a corollary, we obtain the following. Proof. Observe first that, since G has no false-twin vertices, every set of false-twin vertices in Gv has size exactly 2. Let v i , w i for 1 ≤ i ≤ k the k sets of false-twin vertices, such that v is adjacent to v i . Observe now that, since v i and w i are false-twins, they belong to exactly the same bicliques but those bicliques containing the edge vv i . Consider now the subgraph induced by the vertices {v} ∪ {v 1 , v 2 , . . . , v k } ∪ N (v 1 ) ∪ • • • ∪ N (v k ). Clearly, v 1 , v 2 , . . . , v k are not false-twins in this graph. Now, by Lemma 7.3.3, v belongs to k different bicliques. Those bicliques are either bicliques or are contained in bigger bicliques in G, but they do not contain any of the vertices w i . Now, after removing v, these k bicliques are lost in Gv since any other biclique containing any v i contains also w i .

Combining last three results, we obtain the main theorem of the section. It gives a tight lower bound for the number bicliques of a K 3 -free graph without false-twin vertices.

Theorem 7.3.5. Let G be a K 3 -free graph of order n ≥ 4 without false-twin vertices.

Then G has at least n 2 bicliques.

Proof. The proof is by induction on n. For n = 4 the result trivially holds. Suppose n ≥ 5. Now, by Lemma 7.3.1 there is a vertex v contained in a biclique isomorphic to K 1,r . Without losing of generality, we can suppose that v is the center, otherwise we take its unique adjacent vertex in the biclique. Consider the graph G = Gv. We consider the following two cases.

• G is disconnected. Let G 1 , G 2 , . . . , G s be the connected components of G on n 1 , n 2 , . . . , n s vertices respectively. Since G has no false-twin vertices, it can be at most one G i such that n i = 1. Suppose that there are components, G i 1 , G i 2 , . . . .G i with k i 1 , k i 2 , . . . , k i pairs of false-twin vertices. So, by Lemma 7.3.4 we have that G has k i 1 + k i 2 + • • • + k i bicliques less than G. Also, since G is disconnected, v along with at least one vertex of each of the s components is a biclique in G isomorphic to K 1.r that is lost in G , and clearly different than the ones we have just counted. Consider now for each G i j the graph T w(G i j ). Each of these graphs have n i jk i j vertices and no false-twin vertices. If n i j -k i j = 2 then T w(G i j ) = K 2 , and therefore it has 1 biclique, i.e., at least

n i j -k i j 2
bicliques. If n i jk i j ≥ 4, by inductive hypothesis, T w(G i j ) has also at least

n i j -k i j 2
bicliques. Now, for all other G i without false-twin vertices, if n i = 2, G i has, as before, 1 = n i 2 biclique and for n i ≥ 4, by inductive hypothesis, G i has at least n i 2 . If we sum up everything (and suppose the worst case, this is, there exists one G i , say G s , such that n i = 1) we have that the number of bicliques of G is at least

j=1 n i j -k i j 2 + k i j + s-1 i=1,i =i j n i 2 + 1 ≥ j=1 n i j 2 + s-1 i=1,i =i j n i 2 + 1 ≥ s-1 i=1 n i 2 + 1 ≥ n 2
as desired.

• Suppose now that G is connected. Suppose that in G there are k pairs of falsetwin vertices. As before, by Lemma 7.3.4, G has k bicliques less than G. Consider now the graph T w(G ). This graph has nk -1 ≥ 4 vertices and no false-twin vertices, therefore we can apply the inductive hypothesis. So, we have that T w(G) has at least n-k-1 2 bicliques. Therefore G has at least n-k-1 2 +k ≥ n 2 bicliques as desired. Now suppose that G has no false-twin vertices. We have by inductive hypothesis that it has at least n-1 2 bicliques. Finally, since the biclique isomorphic to K 1,r with center at v is lost in G we conclude that G has at least n-1 2 + 1 ≥ n 2 bicliques.

Since we covered all cases the proof is now complete.

Notice that this result directly implies Theorem 7.2.4 for K 3 -free graphs. Also, we obtain this direct corollary. In Chapter 4, we showed that the strong chromatic index is linear in the maximum degree for any k-degenerate graph where k is fixed. This is an extension of the results due to Chang and Narayanan [START_REF] Chang | Strong chromatic index of 2-degenerate graphs[END_REF] where they prove the same for 2-degenerate graphs. As a corollary, our result leaded to considerable improvement of the constants and also gave an easier and more efficient algorithm. We also gave a sketch of the algorithm.

Further, we considered outerplanar graphs. We gave a formula to find exact strong chromatic index for bipartite outerplanar graphs. We also improved the upper bound for the general outerplanar graphs from the 3∆ -3 stated in [START_REF] Hocquard | Strong edge coloring and induced matching[END_REF].

A recent work [START_REF] Kloks | Algorithms for the strong chromatic index of halin graphs, distance hereditary graphs and maximal outerplanar graphs[END_REF] gives an algorithm to find the strong chromatic index of any maximal outerplanar graph, but notice that when you extend the graph to maximal outerplanar, the maximum degree and the index can increase. We provided an algorithm to color any outerplanar graph with number of colors close to optimum and bipartite outerplanar graphs with optimum colors.

In some special cases of the general outerplanar graph, (where we use η extra colors), we were not able to show the optimality of the bounds. We believe that it is very close to the exact bound within an additive factor of a small constant. It would be interesting to prove if our bounds are optimal and if not, to find a way to close the gap.

In Chapters 5 and 6, we studied the existence of proper hamiltonian paths and proper hamiltonian cycles, respectively, in edge-colored multigraphs depending on the number of edges, the rainbow degree and the connectivity. Here, the notable fact is that the proofs were sometimes long and tedious despite the lower bounds for the edges in the considered multigraphs were really high. Finally, we stated Conjecture 6.2.4 that guarantees the existence of a proper hamiltonian cycle in a 2-connected edge-colored multigraph with bounded number of edges and fixed rainbow degree.

It should be also interesting to study similar conditions for other patterns such as trees, etc.

In Chapter 7 we studied different structural properties of bicliques in graphs without false-twin vertices and then, we applied them to the study of the iterated biclique operator. There exists an O(n 4 ) time algorithm to decide if a given graph converges or diverges under the biclique operator and the possible behaviors have been characterized. We proved that graphs with at least 7 bicliques are divergent under the biclique operator. Furthermore, we proved that this sufficient condition implies that graphs with no false-twin vertices that are convergent, have at most 12 vertices, and therefore, there is a finite number of them. We also proposed a linear time algorithm to decide the behavior of a graph under the biclique operator. It is worth mentioning that no polynomial time algorithm is known for deciding the behavior of a graph under the clique operator. Finally, we proved a lower bound of the number of bicliques in K 3 -free graphs without false-twin vertices and we stated Conjecture 7.3.8 for a similiar result for the general case, i.e., the condition of the graph being K 3 -free is dropped. We proposed several results and conjectures that might help to solve the general one.

Figure 3 . 1 :

 31 Figure 3.1: Coloring of K 4,5 . Normal edges represent color 1 and bold edges color 2.

Fact 3 .

 3 2.0.1. A graph G has pc(G) = 1 if and only if G is complete.

Figure 3 . 2 : 3 Proposition 3 . 2 . 3 .

 323323 Figure 3.2: Smallest 2-connected graph with pc(G) = 3

Figure 3 . 3 :

 33 Figure 3.3: Placement of vertices 1.

Figure 3 . 4 :

 34 Figure 3.4: Placement of vertices 2.

Figure 3 . 5 :

 35 Figure 3.5: Placement of vertices 3.

  and for each edge with color 2, different from v 2 v 3 and v 2p-2 v 2p-1 , choose one of the endpoints, say v , and put c(v 1 v ) = 2 (see Fig.3.6). Finally, color the rest of the edges with color 1. We now show that this coloring gives k proper paths between each pair of vertices v and w of G. First, take v = v 1 and w = v 2 (or similarly taking w = v 2p-1 ). We have the edge v 1 v 2 and the path v 1 v 2p-1 v 2 . Now since n = 2p -1 ≥ 2k we have at least (p -1) -2 ≥ k -2 edges in the cycle C with color 2 different from v 2 v 3 and v 2p-2 v 2p-1 and therefore we form the following k -2 proper paths between v 1 and v 2 of the form v 1 v v 2 where v is an endpoint of each of these edges such that c(v 1 v ) = 2. Now take v = v 1 and w = v 3 (analog taking w = v 2p-2 ). This case is similar to the previous except changing the second formed path to v 1 v 2 v 3 . Suppose now that v = v 1 and w = w with w / ∈ {v 2 , v 3 , v 2p-2 , v 2p-1 }. We take the edge v 1 w and now, since there are at least i(p -1) -1 ≥ k -1 edges in the cycle C with color 2 with endpoints different from v , we form the following k -1 proper paths between v 1 and w of the form v 1 v w where v is an endpoint of each of these edges such that c(v 1 v ) = 2. The rest of the cases are similar to those described before in the case n = 2p forming most of the proper paths with length 3.

Figure 3 . 6 :

 36 Figure 3.6: Coloring of K 13 . Normal edges represent color 1 and bold edges color 2.

Theorem 3 .

 3 3.3 ([90]). Let G be a 3-connected graph with n vertices and δ(G) ≥ n/4 + 2.Then, for any longest cycle C in G, every component of G -C has at most two vertices. Theorem 3.3.4 ([42]). Let G be a connected graph with n vertices and δ(G) ≥ n/3. Then one of the following holds: (i) G contains a hamiltonian path. (ii) For any longest cycle C of G, G -C has no edge.Also we use the following easy fact as a matter of course.

Fact 3 . 3 . 4 . 1 .

 3341 Every 2-connected graph G with δ(G) ≥ 2 is either hamiltonian or contains a cycle C with at least 2δ(G) vertices.

  4 and |C 21 | ≤ (3n/4 -1 -|S|)/2 = 3n/8 -(|S| + 1)/2 ≤ 3n/8 -1. Hence by Theorem 3.3.1, C 21 contains a hamiltonian cycle C 21 . Since δ(C 22 ) ≥ n/4 -3, C 22 is either hamiltonian or contains a cycle C 22 with |C 22 | ≥ n/2 -6. Now take a path P 2 with v ∈ endpoints(P 2 ) so that (1) P 2 contains a longer segment of C 2j for each j = 1, 2, and subject to condition (1), (2) |P 2 | is as large as possible.

  2 . If x ∈ C 21 then since |P ∩ C 21 | ≥ |C 21 |/2 and |C 21 | ≤ 3n/8 -1, by the minimum degree condition, x has at least n/4 -3n/16 ≥ 2 edges to P since n ≥ 32. For x ∈ C 22 , we know |C 22 | ≤ n/2 -2 and either C 22 is hamiltonian or contains a cycle of length at least n/2 -6. In either case, the same arguments easily show that x has at least 2 edges to P , meaning that pc(G) = 2. Subcase 1.2: = 3. In this case, by the minimum degree condition, we see that n/4 ≤ |C 1 | ≤ (n -1)/3 ≤ |C 3 | ≤ n/2 -1, and |C 2 | ≤ 3n/8 -1/2. Hence by Theorem 3.3.1, each C i with i = 1, 2

Case 2 :

 2 κ(G) = 2. Let u and v be a minimum cutset of G. Again we let C 1 , C 2 , . . . , C be the components of G \ {u, v} with |C i | ≤ |C j | for i ≤ j and break the rest of the argument into cases based on the value of . Note that, since δ(G) ≥ n/4, we have 2 ≤ ≤ 4. Subcase 2.1: = 4 Since δ(G) ≥ n/4, we know that n

  C 1 and C 2 are both hamiltonian-connected by Theorem 3.3.1. This means we may create a single cycle D 12 using all of C 1 ∪ C 2 . If κ(C 3 ) ≥ 2, then let D 3 be a longest cycle in C 3 . Since δ(C 3 ) ≥ n 4 -2, we know |D 3 | ≥ min{|C 3 |, n 2 -4}. In either case every vertex of C 3 has at least 2 edges to H 3 . Now since G is 2-connected, there exist two disjoint paths from D 12 to D 3 meaning there is a spanning subgraph of G satisfying the conditions of the graph H 5 . By Lemma 3.3.5, we have pc(G) = 2. If κ(C 3 ) = 1, then by Theorem 3.3.4, there is a spanning path P of C 3 . The vertices u and v must each have at least one edge to P so P ∪ D 12 forms a spanning subgraph of G satisfying the conditions of the graph H 6 in Lemma 3.3.5. Hence, pc(G) = 2. Subcase 2.3: = 2

joining v 1

 1 and v j with an edge for each 2 ≤ j ≤ 4. Then the resulting graph G is connected and it has δ(G) = n/4 -1 and pc(G) = 3.

Fact 4 .

 4 1.1.1.

Figure 4 . 1 :

 41 Figure 4.1: Local structure of a partial coloring when edge vw is selected. The dotted edges are yet to be colored and the shaded vertices potentially have colored degree more than k.

( 6 )

 6 If |C| = 5 and every vertex has at least 2 pendant edges, let u, v be the vertices where the max u 1 v 1 ∈E(C) d(u 1 ) + d(v 2 ) is reached and let x, y and z be the rest of the vertices. Call η = d(x)+d(y)+d(z)-d(u)-d(v)-3 2

  Thus we have d(u) + d(v) -6 uncolored edges incident to u and v, and d(x) + d(y) + d(z) -9 uncolored edges incident to x, y and z. Suppose that d(u) + d(v) -6 ≥ d(x) + d(y) + d(z) -9, i.e., d(u) + d(v) ≥ d(x) + d(y) + d(z) -3. We use d(u) -3 new colors to color the uncolored edges at u and d(v) -3 new colors for the ones at v. We remark that this is the only possibility to keep the strong coloring property. Clearly, d(x) ≤ d(u) and d(z) ≤ d(v).

  and therefore we have used at most d(u) + d(v)d(v i ) colors from B to color the edges incident to v i+1 and v i-1 . It follows that we may use the remaining d

  introduce two sets of new colors A and B of sizes d(u) -4 and d(v) -2 respectively. Now, color the rest of the edges as in 8), considering x and y as a single vertex. Clearly, this leads to a strong edge-coloring of G following same arguments as in 6) and 8). We used(u) + d(v) colors if k = 4, and d(u) + d(v) -1 colors otherwise. Second, suppose that d(u) + d(v) < d(x) + d(y) + d(z) -3.We use η (as defined earlier) new colors to color a subset of η edges incident to each of v 1 and v 3 . Again, it is easily seen that d(v 1 = x) and d(v 3 = z) are at least η using the assumed inequalities. Finally to color the rest of the edges, we proceed as in the first case. As before, the coloring is strong by 6) and 8). We used(u) + d(v) + η colors if k = 4,and d(u) + d(v) -1 + η colors otherwise. Theorem 4.2.2. Let G be an outerplanar graph. Then χ s (G) = max{max uv∈E d(u) + d(v) -1, max H∈P χ s (H)}, where P is the set of all induced puffer subgraphs of G. If G is also bipartite, then

Lemma 5 . 1 . 1 . 2 + 4

 51124 Let G be a simple non-colored graph on n ≥ 14 vertices. If m ≥ (n-3)(n-4) and for every vertex x, d(x) ≥ 1, then G has a matching M of size |M | ≥ n-2 2 .

Lemma 5 . 1 . 2 . 2 .Proof.

 5122 Let G c be a 2-edge-colored multigraph on n ≥ 14 vertices. Suppose that for every vertex x in G c , rd(x) = 2. If m ≥ (n-3)(n-4)+3n-2, then G c has two matchings M r and M b on colors, say red and blue, such that |M r | = n 2 and |M b | ≥ n-2 Let us denote E r (G c ) and E b (G c ) the set of edges colored in red and blue, of sizes |E r (G c )| = m r and |E b (G c )| = m b , respectively. Observe that, as for every vertex x in G c , rd(x) = 2, we have that d i (x) ≥ 1 for i ∈ {r, b}.

Lemma 5 . 1 . 4 . 2 . 2 .• ( 2 ) 1 - 2 .• ( 3 ) 2 -

 5142221232 Let G c be a connected c-edge-colored multigraph, c ≥ 2. Let M be a matching of G c in one color, say red, of size |M | ≥ n-2 Let P = x 1 y 1 x 2 y 2 . . . x p y p , p ≥ 2, be a longest proper path compatible with M . Then we have the following cases:• (1) n is even, |M | = n2 and 2p < n -(1a) If there is no proper cycle C such that V (C) = V (P ), then there are at least (n -2 + pn -2p 2 )(c -1) missing edges in G c different from red and the minimum value of this function is (2n -4)(c -1) for p = n-2 2 . -(1b) If there is a proper cycle C such that V (C) = V (P ), then there are at least (2pn-4p 2 )(c-1) missing edges in G c different from red and the minimum value of this function is (2n -4)(c -1) for p = n-2 n is odd, |M | = n-1 2 and 2p < n -(2a) If there is no proper cycle C such that V (C) = V (P ), then there are at least (n -3p + pn -2p 2 )(c -1) missing edges in G c different from red and the minimum value of this function is (2n -6)(c -1) for p = n-3 2 . -(2b) If there is a proper cycle C such that V (C) = V (P ), then there are at least (2pn -2p -4p 2 )(c -1) missing edges in G c different from red and the minimum value of this function is (2n -6)(c -1) for p = n-3 n is even, |M | = n-2 2 and 2p < n -(3a) If there is no proper cycle C such that V (C) = V (P ), then there are at least (n -4 -2p + pn -2p 2 )(c -1) missing edges in G c different from red and the minimum value of this function is (2n -8)(c -1) for p = n-4 2 . -(3b) If there is a proper cycle C such that V (C) = V (P ), then there are at least (2pn -4p -4p 2 )(c -1) missing edges in G c different from red and the minimum value of this function is (2n -8)(c -1) for p = n-42 .

Lemma 5 . 1 . 5 . 2 + 3 ,

 51523 Let G be a connected non-colored simple graph on n vertices, n ≥ 9. If m ≥ (n-2)(n-3) then G has a matching M of size |M | = n 2 .

2 and d b (v) ≥ n+1 2 , 2 - 1 . 2 - 1 ) 2 - 1 red

 22212121 then G c has a proper hamiltonian path. Suppose then than there exists a vertex v such that d r (v) ≤ n+1 Suppose first that there exist two neighbors of v, say u and w, such that c(vu) = r and c(vw) = b. We construct then a new multigraph G c by replacing the vertices v, u and w with a new vertex z such that N r (z) = N r G c -{v,u,w} (w) and N b (z) = N r G c -{v,u,w} (u). We remark that N r G c -{v,u} (w) and N r G c -{v,w} (u) cannot be both empty at the same time, otherwise E(G c ) ≥ n -3 + n -3 + n -( n+1 > 2n -4. A contradiction in the total number of edges. So, by this we remove at most n -1 blue edges and n+1 edges from v, n -3 red edges from u, n -3 blue edges from w, and one red and one blue between u and w. Therefore G c has at least

Lemma 5 . 3 . 1 .

 531 Let G c be a c-edge-colored connected multigraph on n vertices, c ≥ 3 and m ≥ c f (n) + 1 edges. There exists one color c j such that if we color its edges with another used color and we delete parallel edges with the same color, then the resulting (c -1)-edge-colored multigraph is connected and has m ≥ (c -1) f (n) + 1 edges, such that if G c-1 has a proper hamiltonian path then G c has one too. Moreover, if rd(

Theorem 5 . 3 . 3 . 9 and c ≥ 3 . 2 +

 533932 Let G c be a connected c-edge-colored multigraph on n vertices, n ≥ If m ≥ c(n-2)(n-3) n, then G c has a proper hamiltonian path.Proof. By Lemma 5.3.1 it is enough to prove the theorem for c = 3.

2 + 3 .

 23 Since the subgraph in color b is connected because of the rainbow degree of the vertices, we have by Lemma 5.1.5 that there is a matching M b such that |M b | = n 2 for n even and |M b | = n-1

  1.4 we can check that |P | ≥ n -5. The case |P | = n -1 is trivial. Clearly, there are no edges in colors r and g between M b \ (M b ∩ P ) and P . Therefore taking any vertex x in M b \ (M b ∩ P ) we obtain that d(x) ≤ 4 + n -1 = n + 3, for |P | = n -3, and d(x) ≤ 8 + n -1 = n + 7, for |P | = n -5. In both cases, this is less than 2n -6 so we can do the contraction with x.

Theorem 5 . 2 +

 52 3.4 is the best possible for n ≥ 11. In fact, consider a rainbow complete multigraph, say A, on n -2 vertices. Add 2 new vertices v 1 , v 2 and then join them to a vertex v of A with all possible colors. The resulting c-edge-colored multigraph has c(n-2)(n-3) 2c edges and clearly has no proper hamiltonian path. If n = 6, 8, the graphs H c k,k+2 , k = 2, 3, are exceptions for Theorem 5.3.4.

1 . 2 Lemma 6 . 1 . 1 .

 12611 Assume that G c contains a proper cycle C, of length at most n -2 and that there exists a red edgexy in G c -C. If d b C (x) + d b C (y) > |C|, then G c has a proper cycle of length |C| + 2 containing xy. Proof. Set C = x 1 y 1 x 2 y 2 . . . x s y s x 1 , where x i y i are the red edges of C, i = 1, 2, . . . , s. Then d b {x i ,y i } (x)+d b {x i ,y i } (y) ≤ 2, otherwise if d b {x i ,y i } (x)+d b {x i ,y i } (y) ≥ 3, then we have that the cycle x 1 y 1 x 2 y 2 . . . x i xyy i . . . x s y s x 1 is the desired one. It follows that i d b {x i ,y i } (x) + d b {x i ,y i } (y) ≤ 2 |C| 2 =|C|, a contradiction to the hypothesis of the lemma. This completes the proof. Now we can prove the following theorem. Theorem 6.1.2. Let G c be a 2-edge-colored multigraph on n vertices, n ≥ 4. If m ≥ (n -1)(n -2) + n, then G c has a proper hamiltonian cycle if n is even, and a proper cycle of length n -1 otherwise.

2 and d b (x) ≥ n+1 2 , 2 - 1 .

 2221 then G c has a proper hamiltonian cycle for n even and a proper cycle of length n -1 for n odd. Let us suppose therefore that for some vertex, say x, and for some color, say red, d r (x) ≤ n+1Notice now that d r (x) > 0 and d b (x) > 0, otherwise, for example if d r

2 - 1

 21 again a contradiction. Thus we may conclude that there are two distinct neighbors, say y and z, of x such that c(xy) = r and c(xz) = b in G c . Replace now the vertices x, y, z by a new vertex s such that N b (s) = N b G c -{x,y,z} (y) and N r (s) = N r G c -{x,y,z} (z). The obtained graph, say G , has n -2 vertices and at least (n -1)(n -2) + n -[(n -1) + n+1 + 2(n -2)] = n 2 -11n 2 + 8 > n 2 -6n + 8 edges, i.e., the number of edges needed for the inductive hypothesis in a graph on n -1 vertices. So, G has a proper hamiltonian cycle for n -2 even and a proper cycle of length n -3 otherwise. If G has a proper hamiltonian cycle then coming back to G c we may easily find a proper hamiltonian cycle in G c . Assume now that n -2 (and thus n) is odd. Let C be a proper cycle of length n -3 in G . If s belongs to C, then as previously we may easily find a proper cycle of length n -1 in G c . Assume therefore that s does not belong to C. By Lemma 6.1.1, if d b C (x) + d b C (y) > |C| or d r C (x) + d r C (z) > |C|) then we may integrate the edge xy (respectively xz) in C in order to obtain a cycle of length n -1. Assume therefore that d b C b(x) + d b C (y) ≤ |C| and d r C (x) + d r C (z) ≤ |C|. But then the number of edges of G c is at most n

Theorem 6 . 2 . 3 . 2 +

 6232 Let G c be a c-edge-colored multigraph on n vertices, n ≥ 4 and c ≥ 3.Assume that for every vertex x of G c , rd(x) = c. If m ≥ c(n-1)(n-2) c + 1, then G c has a proper hamiltonian cycle.

Conjecture 6 . 2 . 4 .

 624 Let G c be a 2-connected c-edge-colored multigraph on n vertices, n ≥ 10 and c ≥ 3. Assume that for every vertex x of G c , rd(x) = c. If m ≥ c(n-2)(n-3) 2 +4c+1, then G c has a proper hamiltonian cycle.

Proposition 7 . 1 . 3 (

 713 [START_REF] Groshaus | On the iterated biclique operator[END_REF]). For any graph G, we have KB(G) = KB(T w(G)).Next theorem characterize the behavior of a graph under the biclique operator.Theorem 7.1.4 ([53]). If KB(G) contains either K 5 or the gem or the rocket as an induced subgraph, then G is divergent. Otherwise, G converges to K 1 or K 3 in at most 3 steps.

Corollary 7 . 1 . 5 (

 715 [START_REF] Groshaus | On the iterated biclique operator[END_REF]). A graph G is convergent if and only if T w(KB(G)) has at most four vertices. Moreover, T w(KB(G)) = K n for n = 1, ..., 4.

Lemma 7 . 2 . 1 .

 721 Let G = KB(H) for some graph H. Let b 1 , b 2 be false-twin vertices of G and B 1 , B 2 their associated bicliques in H. Suppose that there are no edges between vertices of B 1 and vertices of B 2 . Then there exists a vertex v ∈ H such that v is adjacent to every vertex of B 1 and B 2 . Furthermore, G contains a K 5 as induced subgraph. Proof. Let b 1 , b 2 be false-twin vertices of G and B 1 , B

Lemma 7 . 2 . 2 .

 722 Let G = KB(H) for some graph H. Let b 1 , b 2 , b 3 be false-twin vertices

Theorem 7 . 2 . 3 .

 723 Let G be a graph. If G has at least 7 bicliques, then G diverges under the biclique operator. Proof. By way of contradiction, suppose that G has at least 7 bicliques and G converges under the biclique operator. By Corollary 7.1.5, T w(KB(G)) = K n for n = 1, ..., 4.

Theorem 7 . 2 . 4 .

 724 Let G be a graph with no false-twin vertices. If G has at least 13 vertices then G has at least 7 bicliques.

  to prove. Now the proof is complete. Theorem 7.2.4 implies that the number of convergent graphs without false-twin vertices is finite since convergent graphs without false-twin vertices have at most 12 vertices. This fact leads to the following linear time algorithm.Algorithm: Given a graph G, build H = T w(G). If H has at least 13 vertices, answer "G diverges" and STOP. Otherwise, build T w(KB(H)). If T w(KB(H)) has at most 4 vertices answer "G converges" and STOP. Otherwise, answer "G diverges" and STOP. The algorithm has O(n + m) time complexity. For this, observe that H can be built in O(n + m) time by the known modular decomposition and if H has at most 12 vertices any further operation takes O(1) time complexity.

Lemma 7 . 3 . 1 .

 731 Let G be a K 3 -free graph without false-twin vertices. Then every vertex is contained in a biclique isomorphic to K 1,r for some r ≥ 1.Proof. Let v be a vertex. If |N (v)| = 1 then the result clearly follows. Suppose now that |N (v)| > 1. Now, since N (v) is an independent set, {v} ∪ N (v) is contained in one biclique. If there is no vertex w such that N (v) ⊆ N (w) then {v} ∪ N (v) is a biclique isomorphic to K 1,r , r = |N (v)|.Otherwise, let u be the vertex with maximum degree among all vertices in N (v). Clearly, since G is K 3 -free and without false-twin vertices, if there are two vertices of same maximum degree, they must have some different neighbors. Therefore, {u} ∪ N (u) is a biclique isomorphic to K 1,r , r = |N (u)| and contains the vertex v as desired.

Corollary 7 . 3 . 2 .

 732 Let G be a graph without false-twin vertices. Let v be a vertex such that d(v) = ∆(G) and v does not belong to a K 3 . Then {v} ∪ N (v) is a biclique.

Lemma 7 . 3 . 3 .

 733 Let G be a K 3 -free graph without false-twin vertices. Let v be a vertex such that d(v) = k. Then v belongs to at least k different bicliques.

Corollary 7 . 3 . 4 .

 734 Let G be a K 3 -free graph without false-twin vertices. Suppose that there is a vertex v such that the graph Gv has k sets of false-twin vertices. Then Gv has at least k bicliques less than G.

Corollary 7 . 3 . 6 .

 736 Let T be a tree of order n ≥ 4 without false-twin vertices. Then T has at least n 2 bicliques. Following Corollary 7.3.6 we obtain this immediat result. Corollary 7.3.7. For n 2 ≤ k ≤ n -2 and n ≥ 4 there exists a tree T without false-twin vertices of order n and k bicliques. Now, we state the following conjecture that generalizes Theorem 7.3.5. Conjecture 7.3.8. Let G be a graph without false-twin vertices of orden n. Then G has at least n 2 bicliques.

  The graph H 4 obtained from an even cycle C and two paths P 1 and P 2 by identifying an end of each path to a vertex of C. As in H 3 , we may also join vertices each with at least 2 edges to either a path P i or C.(5) The graph H 5 obtained from the union of two disjoint cycles which are connected by two disjoint paths to form a 2-connected graph. Furthermore, we may also add vertices each with at least 2 edges to this structure.[START_REF] Andersen | The strong chromatic index of a cubic graph is at most 10[END_REF] The graph H 6 obtained from H 5 by removing an edge from one of the cycles. Again we may add vertices each with at least 2 edges to this structure.Proof. One can easily get a 2-coloring of H i which forces pc(H i ) = 2 for i = 1, 2, . . . , 6.For example, as for H 1 , by Fact 3.2.0.2 and Proposition 3.2.1, there is a 2-coloring of H 1 that is properly connected.We are now ready to prove our main result. G contains a spanning subgraph which satisfies the properties of H 3 in Lemma 3.3.5 so pc(G) = 2. Thus we may assume that κ(C 2 ) = 1 or 2. Let S be a cutset in C 2 with 1 ≤ |S| ≤ 2. By the minimum degree condition, it is easy to check that there are exactly two components C 21 , C 22 with |C 21

The graph H 2 obtained from a path P with |P | ≥ 1 and even cycle C by identifying exactly one vertex (i.e., |P ∩ C| = 1).

(3) The graph H 3 obtained from H 2 and m ≥ 0 isolated vertices v 1 , . . . , v m by joining each v i for (i ≤ m) with at least two edges to either P -C or C -P in H 2 .

(4)

Theorem 3.3.6. If G is a connected non-complete graph with n ≥ 68 vertices and δ(G) ≥ n/4, then pc(G) = 2.

Proof. If κ(G) ≥ 3, then by Corollary 3.1.7, we have pc(G) = 2. So we may assume that κ(G) = 1 or 2. We divide the proof into two cases according to the value of κ(G). Case 1: κ(G) = 1. Let v be a cutvertex of G and let C 1 , . . . , C be the components of G \ v such that |C 1 | ≤ . . . ≤ |C |. By the minimum degree condition, we see that = 2 or 3 and |C 1 | ≥ n/4. We further divide the proof into two subcases: Subcase 1.1: = 2.

In this case note that |C 1 | ≤ (n -1)/2 and, by the minimum degree condition, |C 2 | ≤ 3n/4 -1. Utilizing Theorem 3.3.1 and the minimum degree condition, it is easy to check that {v}∪C 1 contains a hamiltonian path P 1 such that v ∈ endpoints(P 1 ). If κ(C 2 ) ≥ 3, then let C be a longest cycle of C 2 . Since G is connected, there is a path P from v to C. Now H = P 1 ∪ P ∪ C satisfies the conditions of H 2 in Lemma 3.3.5. This means that pc(H) = 2. By Theorem 3.3.3, every component of C 2 \ C has at most 2 vertices. By the minimum degree condition and since we assume n ≥ 12, for each x ∈ C 2 \ H, we have |E(x, H)| ≥ n 4 -1 ≥ 2. Hence,

  The graph G is 2-connected so there are two independent edges from {u, v} to each component C i . With n ≥ 26, we see that|C i | ≥ 6 so the minimum degree condition δ(C i ) ≥ |C i | -2 implies, by Theorem 3.3.2, that each component C i is panconnected. This means that, if |C 3 ∪ C 4 |is even, we may find a cycle through {u, v}∪C 3 ∪C 4 using all the vertices, and if |C 3 ∪C 4 | is odd, we may find a similar cycle which misses exactly one vertex w ∈ C 4 . This cycle, along with a spanning path of u ∪ C 1 ∪ C 2 and possibly w provides a spanning subgraph of G satisfying the properties of H 3 from Lemma 3.3.5, meaning that pc

  2 their associated bicliques in H, such that there are no edges between vertices of B 1 and vertices of B 2 . Since G is connected, take the shortest path from some vertex of B 1 to B 2 . Let w be the first vertex in the path such that w / ∈ B 1 . Clearly, w / ∈ B 2 . Let v ∈ B 1 be a vertex adjacent to w. Suppose that there exists a vertex x ∈ B 1 such that x is not adjacent to w. Then consider the following alternatives: Case 1: xv ∈ E(H). Then, {x, v, w} is contained in some biclique B, B = B 1 and B = B 2 , that does not intersect B 2 since there is no edge between B 1 and B 2 . A contradiction, because b 1 and b 2 are false-twin vertices.

Case 2: xv / ∈ E(H). Then there exists a vertex y ∈ B 1 adjacent to v and x. If y is adjacent to w, similar to Case 1, we have that {x, y, w} is contained in a biclique B, B = B 1 and B = B 2 , that does not intersect B 2 , a contradiction. Now, if y is not adjacent to w, {y, v, w} is contained in a biclique B, B = B 1 and B = B 2 , that does not intersect B 2 , a contradiction.

  Let u ∈ B 1 , v ∈ B 2 , w ∈ B 3be the K 3 . Now, uv, uw and uw are contained in 3 different bicliques of H. Since the biclique that contains uv has to intersect B 3 there exists a vertex z ∈ B 3 adjacent to v and not adjacent to u. Consider the cases:Case 1.1: zw / ∈ E(H). Since the biclique that contains uw has to intersect B 2 there exists a vertex x ∈ B 2 adjacent to w and not adjacent to u. Now we have more cases: Case 1.1.1: xv ∈ E(H), xz ∈ E(H). Then we have that H contains the gem {u, v, z, x, w} as induced subgraph and therefore there is a K 5 in G. Case 1.1.2: xv ∈ E(H), xz / ∈ E(H). As B 1 is a biclique, then there exists a vertex u ∈ B 1 adjacent to u. Now, it is easy to see that if we add any number of edges from u to the other vertices we form 4 bicliques mutually intersecting and taking B 1 , B 2 or B 3 we obtain a K 5 in G. It is easy to see that if we add any number of edges from u to the other vertices we form 4 bicliques mutually intersecting and taking B 1 , B 2 or B 3 we obtain a K 5 in G. We covered all the cases when a K 3 is in H. Case 2: There is an induced C 4 in H with two vertices in B 1 , one in B 2 and one in B 3 . Let u, x ∈ B 1 , v ∈ B 2 , w ∈ B 3 be the C 4 , that is ux, uv, vw, xw ∈ E(H). As B 2 is a biclique there exists a vertex v ∈ B 2 adjacent to v, such that v does not extend the C 4 . Then, v cannot be adjacent to x and not adjacent to u and w. We have the following cases: Case 2.1: if v is adjacent to x and w or adjacent to u and w we have a triangle and we already covered that case. Case 2.2: v is only adjacent to u and x. Now as B 3 is a biclique there exists a vertex w ∈ B 3 adjacent to w such that w does not extend the C 4 . Then, it is easy to see that if we add any number of edges from w to the other vertices we obtain either four mutually intersecting bicliques or a triangle. Therefore a K 5 is present in G. Case 2.3: v is only adjacent to w. As B 1 is a biclique there exists a vertex x ∈ B 1 adjacent to x such that x does not extend the C 4 . As in the previous case, we can see that adding any number of edges from x to the other vertices we obtain either four mutually intersecting bicliques or a triangle. So, a K 5 in G. Case 2.4: v is not adjacent to any one of the other vertices (only to v). Now, as B 3 is a biclique there exists a vertex w ∈ B 3 adjacent to w such that does not extend the C 4 . Then w cannot be adjacent to any vertex different of v because if that happens we are in one of the cases 2.1, 2.2 or 2.3. So, if w is adjacent to v we have that the sets {u, x, v, w}, {v, v , w, w }, {u, v, v , w} and {x, w, w , v} are contained in four different bicliques and they are mutually intersecting, so G contains a K 5

Case 1.1.3: xv / ∈ E(H), xz / ∈ E(H). Then we have that {u, v, z}, {w, v, z}, {v, w, x} and {u, w, x} are contained in 4 different intersecting bicliques and therefore, counting one of the bicliques B 1 , B 2 or B 3 we have that K 5 is in G. Case 1.1.4: xv / ∈ E(H), xz ∈ E(H). As B 2 is a biclique there exists a vertex x ∈ B 2 adjacent to x and v such that x has to be also adjacent to w or z or both since B 2 ∩B 3 = ∅. If x is adjacent to w we have two cases. First, if x is not adjacent to u then H contains the gem {u, w, v, x, x } as induced subgraph and therefore G contains a K 5 . Second, if x is adjacent to u, the same set of vertices induces a house in H and so K 5 is present in G. Now, if x is adjacent to z and not adjacent to w we have this four sets contained in different bicliques mutually intersecting, {v, x, x , w}, {z, x, w, v}, {v, z, u} and {u, w, x}. Finally, taking one of B 1 , B 2 or B 3 , G contains a K 5 . Case 1.2: zw ∈ E(H). Since B 1 is a biclique there exists a vertex u ∈ B 1 adjacent to u.

Acknowledgements

Suppose finally that z = s. As we deleted at most 6n -19 edges, the new graph has at least 3(n-2)(n-3) 2 + n -6n + 19 = 3(n-4)(n-5) 2 + n -2 edges in the component of n -3 vertices. As we will see in next chapter, this component has a proper hamiltonian cycle (Theorem 6.2.2) and therefore it is trivial to add the three contracted vertices to obtain a proper hamiltonian path for the initial graph. Now as the connectivity is proved the theorem holds.

Theorem 5.3.3 is the best possible. Indeed, consider a rainbow complete graph on n -2 vertices with c colors and add two new vertices x and y. Add now the edge xy and also all edges between y and the complete graph, all on a same color. The resulting graph, although it has c (n-2)(n-3) 2 + n -1 edges, it contains no proper hamiltonian path, as x cannot belong to such a path. In conclusion we have at least 6 missing edges in color b and 6n -22 in colors r and g, that gives us a total of 6n -16 missing edges. To find the last one to get a contradiction suppose that there are the parallel edges x 1 y 1 and x p y p in colors r and g, then we can make a proper cycle of length n -1: x 1 y 1 . . . x p y p vyxux 1 , if we also have the edges, y p v and ux 1 in color b, xu and yv in color r or g. Now, as it is trivial to attach the unmatched vertex to the proper cycle there is at least one of those edges missing and therefore a contradiction. If |P | = n -3, we have as before that d r,g P (x) ≤ n -5. As always, there are no parallel edges to the edge xy in colors r and g. Now, if there are no edges between xy and the unmatched vertex z in color r and g, then d(x) ≤ 2n -6 as desired for the contraction. Otherwise, if there are edges in colors r and g to the vertex z, then there cannot be the edges in color b parallel to them since we could replace xy by one of those and thus come back to the previous case. Therefore, we have that d(x) ≤ 2n -5 and d(y) ≤ 2n -5. Then, we can choose for the contraction, either x Theorem 6.1.3. Let G c be a 2-edge-colored multigraph on n vertices, n ≥ 9. Assume that for every vertex

has a proper hamiltonian cycle if n is even, and a proper cycle of length n -1 otherwise.

Proof. The proof is by induction on n. For n = 9, 10, by inspection the result holds. Suppose now that n ≥ 11. Observe that E(G c ) ≤ 2n -6. By a Theorem of [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], if for every vertex v ∈ G c we have that d r (v) ≥ n+1

. Suppose first that d r (v) ≤ 2 and that in G c there exists a vertex x with rd(x) < 2. Therefore in G c either d r (x) ≤ 2 or d b (x) ≤ 2. This vertex clearly cannont be v. Observe first that in both cases E(G c ) = 2n -6, and this happens when both v and x have their colored degrees exactly 2, otherwise we have a contradiction on the total number of edges. So G c must have all possible edges but those edges already missing at v and x. We have the following cases now, depending on the vertex x.

• x = u, therefore d r (u) = 2, u is adjacent in red to v and to w. Now, since G c -{v, u} is rainbow complete it has a proper hamiltonian cycle if n is even and a proper cycle of length n -3 otherwise. Take an blue edge x 1 x 2 of that cycle. Now, since v and u have all possible blue edges, we just add the red edge vu to the cycle joining v with x 1 and u with x 2 in blue and removing the edge x 1 x 2 . Like this we obtain a proper hamiltonian cycle if n is even, and a proper cycle of length n -1 otherwise.

• x = w, therefore d b (w) = 2, w is adjacent in blue to v and to u. Again, since G c -{v, w} is rainbow complete it has a proper hamiltonian cycle if n is even and a proper cycle of length n -3 otherwise. For n odd, we can choose the proper cycle of length n -3 such that there is the second vertex z such that z is adjacent to v in red. Let y be the vertex in the cycle adjacent to z in color red. So, we add the blue edge vw to the cycle joining v to z, w to y both in red, and removing the edge zy. Observe that this is always possible since w is adjacent in red to every vertex. Then we obtain the desired proper hamiltonian cycle for n even, or the proper cycle of length n -1 for n odd.

Chapter 7 Bicliques and Graphs Without False-Twins Vertices

This chapter is organized as follows: In Section 7.1 we present known results about the convergence and divergence of the biclique operator, along with the O(n 4 ) algorithm. In Section 7.2 We prove several results that imply a linear time algorithm for deciding the behavior of a graph under the biclique operator. Finally, in Section 7.3 we study structural properties of bicliques in false-twin free graphs. We assume, unless we clarify, that all graphs in this chapter are connected.

Preliminary results

We start with this easy observation.

Observation 7. 1.1 ([53]). If G is and induced subgraph of H, then KB(G) is a subgraph (not necessarily induced) of KB(H).

The following proposition is central for characterize convergent and divergent graphs under the biclique operator.

Proposition 7.1.2 ([53]

). Let G be a graph that contains K n as a subgraph, for some

As in [START_REF] Groshaus | On the iterated biclique operator[END_REF], consider all maximal sets of false-twin vertices Z 1 , ...Z k and let {z 1 , z 2 , ..., z k } be the set of respresentative vertices such that z i ∈ Z i . The graph obtained by the deletion of all vertices of Z i \ {z i }, for i = 1...k is denoted Tw(G). Observe that T w(G) has no false-twin vertices.

We remark that we verified this conjecture for all graphs without false-twin vertices up to 13 vertices. Note that this is exactly the basic step for the induction in Theorem 7.2.4. We could prove the conjecture if similar results as we have for K 3 -free graphs are valid for general graphs. In particular, if the following conjectures are true, we have a proof of Conjecture 7.3.8 Conjecture 7.3.9. Let G be a graph without false-twin vertices. Then there exists at least one biclique isomorphic either to K 1,r , r ≥ 1, or to K 2,p , p ≥ 2. Our main goal to prove Conjecture 7.3.8 was to prove that we always have a biclique isomorphic either to K 1,r , r ≥ 1, or to K 2,p , p ≥ 2. Having this result, we can always remove one or two vertices in order to obtain a graph with less bicliques than the original and then obtain the result by induction as in Theorem 7.3.5.

Because of this we have the following results that guarantee the existence of a biclique isomorphic either to K 1,r , r ≥ 1, or to K 2,p , p ≥ 2 for special classes of graphs.

Lemma 7.3.12. Let G be a graph without false-twin vertices. Let v 1 v 2 v 3 v 4 be an induced C 4 . If no vertex of the C 4 belongs to a K 3 then are there two bicliques isomorphic to K 1,r 1 and K 1,r 2 , for some r 1 , r 2 ≥ 1.

Proof. Since G has no false-twin vertices There exist without losing of generality, one vertex u 1 adjacent to v 1 not adjacent to the others v i and another vertex u 2 adjacent to v 2 not adjacent to all others v i . Clearly

are in bicliques isomorphic to K 1,r 1 and K 1,r 2 , we are done. Otherwise there are vertices w 1 = w 2 that extend them respectively. This is w 1 is not adjacent to v 1 but adjacent to u 1 , v 2 and v 4 , and w 2 is not adjacent to v 2 but adjacent to u 2 , v 1 and v 3 . We have then that, if {v 1 } ∪ {u 1 , v 2 , v 4 , w 2 } and {v 2 } ∪ {u 2 , v 1 , v 3 , w 2 } are in bicliques isomorphic to K 1,r 1 and K 1,r 2 , we are done. Otherwise, as before, we have two vertices z 1 = z 2 that extend them. But then we have that {v

bicliques. If they are not isomorphic to K 1,r 1 and K 1,r 2 we have again two different vertices that extend them. Finally, since G is finite, at some point we will have no more vertices to extend them and therefore the result holds. Lemma 7.3.13. Let G be a graph without false-twin vertices. Let v be a vertex such that v does not belong to an induced C 4 . Then v belongs to a biclique isomorphic to K 1,r , r ≥ 1.

Lemma 7.3.14. Let G be a graph without false-twin vertices. Let v be an universal vertex.

Then v belongs to a biclique isomorphic to K 1,r , r ≥ 1.

Notice that last lemma is also true when the graph has false-twin vertices.

Lemma 7.3.15. Let G be a graph without false-twin vertices. Let v be a vertex such that N (v) = K p , p ≥ 1 then v belongs to a biclique isomorphic to K 1,r , r ≥ 1.

Lemma 7.3.16. Let G be a graph without false-twin vertices. If G has a K p , p ≥ 1, as a cut-set, then there exists a biclique isomorphic to K 1,r , r ≥ 1.

Lemma 7.3.17. Let G be a graph without false-twin vertices. Let v, w be two non-adjacent vertices such that G -{v, w} is disconnected. Then, there exists a biclique isomorphic either to K 1,r , r ≥ 1, or to K 2,p , p ≥ 2

To finish this chapter, we present the following results about the structure of graphs without false-twin vertices.

Lemma 7.3.18. Let G be a graph without false-twin vertices. If G has a K 3 as a subgraph then there is no vertex that belongs to all bicliques. Lemma 7.3.19. Let G be a graph without false-twin vertices. There are at most two vertices v, w that belong to all bicliques and they must be adjacent. Moreover, for every other vertex u, u is adjacent to v if and only if u is not adjacent to w. From last lemma, we obtain this immediat result.

Chapter 8

Conclusions and Perspectives

In the present thesis, we studied different problems in edge-colorings and in edge-colored multigraphs. In particular, we studied the proper connection number of graphs, strong edge-colorings in k-degenerate and outerplanar graphs, and proper hamiltonian paths and cycles in edge-colored multigraphs. Finally, we studied properties of bicliques of graphs and, in particular, we gave a linear time algorithm to recognize convergent and divergent graphs under the biclique operator

Contribution summary

In Chapter 3 we studied proper connection in graphs. We proved several upper bounds for pc k (G). We stated some conjectures for general and bipartite graphs, Conjectures 3.2.6 and 3.1.1 respectively, and we proved them for the case when k = 1. In particular, we proved a variety of conditions on G which imply pc(G) = 2. We can remark that, from Theorem 3.3.6, it is clear that if G is 2-connected and δ(G) ≥ n 4 , then pc(G) = 2. We believe that this degree condition can be greatly improved in the 2-connected case. In particular, we propose the following conjecture. By the proof of Theorem 3.2.2 and the standard ear decomposition of a 2-connected graph, it is easy to produce a linear-time algorithm to 3-color any 2-connected graph to be proper connected with the strong property. Also since there is an O(n + m) algorithm for finding a block decomposition of a graph G with κ(G) = 1 on n vertices with m edges, we can find an O(n+m) algorithm to produce a proper connected coloring of such graphs. Therefore, in practice, these colorings are not difficult to find.