Une contribution à la théorie des graphes (signés) borne d'homomorphisme et hamiltonicité
Time: 14:00 -- Location: LRI, 435, salle des theses
Cette soutenance aura lieu le mercredi 04 mai 2016 à 2:30pm en Salle 435 du LRI, Bâtiment 650 Ada Lovelace.
Le jury sera composé de:
Mme Liying KANG Professor Shanghai University (Examinateur)
M. Hao LI Directeur de Recherche CNRS Université Paris-Sud (Directeur de thèse)
M. Yannis MANOUSSAKIS Professor Université ParisSud (Examinateur)
M. Reza NASERASR Chargé de Recherche CNRS Université Paris Diderot (CoDirecteur de thèse)
M. Éric SOPENA Professor Université de Bordeaux (Rapporteur)
M. Mariusz WOZNIAK Professor AGH University of Science and Technology (Rapporteur)
English abstract: In this thesis, we study two main problems in graph theory: homomorphism problem of planar (signed) graphs and Hamiltonian cycle problem.
As an extension of the Four-Color Theorem, it is conjectured that every planar consistent signed graph of unbalanced-girth \(d+1(d\geq 2)\) admits a homomorphism to signed projective cube \(SPC(d)\) of dimension \(d\). It is naturally asked that:
Is \(SPC(d)\) an optimal bound of unbalanced-girth \(d+1\) for all planar consistent signed graphs of unbalanced-girth \(d+1\)?
In Chapter 2, we prove that: if \((B, \Omega)\) is a consistent signed graph of unbalanced-girth \(d\) which bounds the class of consistent signed planar graphs of unbalanced-girth \(d\), then \(|B|\geq 2^{d-1}\). Furthermore, if no subgraph of \((B, \Omega)\) bounds the same class, \(\delta (B)\geq d\), and therefore, \(|E(B)|\geq d\cdot 2^{d-2}\). Our result shows that if the conjecture above holds, then the \(SPC(d)\) is an optimal bound both in terms of number of vertices and number of edges.
When \(d=2k\), the problem is equivalent to the homomorphisms of graphs: is \(PC(2k)\) an optimal bound of odd-girth \(2k+1\) for \(\mathcal{P}_{2k+1}\) (the class of all planar graphs of odd-girth at least \(2k+1\)) ? Note that \(K_4\)-minor free graphs are planar graphs, is \(PC(2k)\) also an optimal bound of odd-girth \(2k+1\) for all \(K_4\)-minor free graphs of odd-girth \(2k+1\) ? The answer is negative, in a manuscript, a family of graphs of order \(\mathcal{O}(k^2)\) bounding the \(K_4\)-minor free graphs of odd-girth \(2k+1\) were given. Is this an optimal bound? In Chapter 3, we prove that: if \(B\) is a graph of odd-girth \(2k+1\) which bounds all the \(K_4\)-minor free graphs of odd-girth \(2k+1\), then \(|B|\geq \frac{(k+1)(k+2)}{2}\). Our result together with the result above shows that order \(\mathcal{O}(k^2)\) is optimal.
Furthermore, if \(PC(2k)\) bounds \(\mathcal{P}_{2k+1}\), then \(PC(2k)\) also bounds \(\mathcal{P}_{2r+1}\) \((r > k)\). However, in this case we believe that a proper subgraph of \(PC(2k)\) would suffice to bound\(\mathcal{P}_{2r+1}\), then what's the optimal subgraph of \(PC(2k)\) that bounds \(\mathcal{P}_{2r+1}\) ? The first case of this problem which is not studied is \(k=3\) and \(r=5\). For this case, Naserasr conjectured that the Coxeter graph bounds \(\mathcal{P}_{11}\). Supporting this conjecture, in Chapter 4, we prove that the Coxeter graph bounds \(\mathcal{P}_{17}\).
In Chapters 5,6, we study the Hamiltonian cycle problems. Dirac showed in 1952 that every graph of order \(n\) is Hamiltonian if any vertex is of degree at least \(\frac{n}{2}\). This result started a new approach to develop sufficient conditions on degrees for a graph to be Hamiltonian. Many results have been obtained in generalization of Dirac's theorem. In the results which strengthen Dirac's theorem, there is an interesting research area: to control the placement of a set of vertices on a Hamiltonian cycle such that these vertices have some certain distances among them on the Hamiltonian cycle.
In this thesis, we consider two related conjectures, one is given by Enomoto: if \(G\) is a graph of order \(n\geq 3\) and \(\delta(G)\geq \frac{n}{2}+1\), then for any pair of vertices \(x\), \(y\) in \(G\), there is a Hamiltonian cycle \(C\) of \(G\) such that \(dist_C(x,y)=\lfloor \frac{n}{2}\rfloor\). Motivated by this conjecture, it is proved that a pair of vertices are located at distances no more than \(\frac{n}{6}\) on a Hamiltonian cycle. Considering the cases \(\delta(G)\geq \frac{n+k}{2}\), \(2\leq k\leq \frac{n}{2}\), Faudree and Li proved that a pair of vertices can be located at any given distance from \(2\) to \(k\) on a Hamiltonian cycle. Moreover, Faudree and Li proposed a more general conjecture: if \(G\) is a graph of order \(n\geq 3\) and \(\delta(G)\geq \frac{n}{2}+1\), then for any pair of vertices \(x\), \(y\) in \(G\) and any integer \(2\leq k \leq \frac{n}{2}\), there is a Hamiltonian cycle \(C\) of \(G\) such that \(dist_C(x,y)= k\).
Using Regularity Lemma and Blow-up Lemma, in Chapter 5, we give a proof of Enomoto's conjecture for graphs of sufficiently large order, and in Chapter 6, we give a proof of Faudree and Li's conjecture for graphs of sufficiently large order.