This thesis consists in successive glimpses of different problems in discrete mathematics related to graph theory. Its mains focus is on graph colouring, i.e. on assignments of integer values to the vertices (or edges) of a graph satisfying a set of local constraints, most of the time the exclusion of specific patterns in the coloured graph....
-
October 20, 2011 (v1)PublicationUploaded on: December 3, 2022
-
January 10, 2019 (v1)Publication
In this document are given Linear Program formulations of several graph problems related to the acyclicity constraints without the use of constraint generations.
Uploaded on: December 4, 2022 -
December 12, 2017 (v1)Journal article
Dans un graphe, existe-t-il un circuit visitant chaque sommet une fois et une seule ? Une question difficile pour certains graphes...Cet article explique comment les auteurs ont abordé et remporté la compétition internationale organisée par la Flinders University d'Adelaïde (Australie), intitulée FHCP Challenge, sur le problème du cycle...
Uploaded on: February 28, 2023 -
February 24, 2010 (v1)Report
A proper vertex colouring of a graph $G$ is {\it 2-frugal} (resp. {\it linear}) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph $G$ is {\it 2-frugally} (resp. {\it linearly}) {\it $L$-colourable} if for a given list assignment $L:V(G)\mapsto 2^{\mathbb N}$, there exists...
Uploaded on: December 4, 2022 -
2016 (v1)Journal article
Caro, West, and Yuster studied how r-uniform hypergraphs can be oriented in such a way that (generalizations of) indegree and outdegree are as close to each other as can be hoped. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof.
Uploaded on: February 28, 2023 -
2018 (v1)Journal article
If G be a graph or a digraph, let id(G) be the minimum size of an identifying code of G if one exists, and id(G) = +∞ otherwise. For a graph G, let idor(G) be the minimum of id(D) overall orientations D of G. We give some lower and upper bounds on idor(G). In particular, we show that idor(G) <= 3/2 id(G) for every graph G. We also show that...
Uploaded on: February 27, 2023 -
November 2010 (v1)Journal article
We give a short proof of the following theorem due to Borodin (1990). Every planar graph G with maximum degree at least 9 is (Δ(G)+1)-edge-choosable.
Uploaded on: February 28, 2023 -
2011 (v1)Journal article
A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L : V(G) → N, there exists a 2-frugal (resp. linear) colouring c of G such that...
Uploaded on: February 28, 2023 -
2009 (v1)Report
We give a short proof of the following theorem due to Borodin~\cite{Bor90}. Every planar graph with maximum degree $\Delta\geq 9$ is $(\Delta+1)$-edge-choosable.
Uploaded on: December 4, 2022 -
May 28, 2013 (v1)Conference paper
Nous proposons un algorithme simple et efficace pour calculer l'hyperbolicité de grands graphes dont la complexité temporelle est fonction de la distribution des plus courts chemins dans les composantes biconnexes du graphe et de la valeur de l'hyperbolicité. Nous montrons également comment réduire la taille de l'instance en utilisant une...
Uploaded on: December 2, 2022 -
2009 (v1)Report
A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an {\it acyclic edge-colouring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-colouring} with $k$ colours. We conjecture that if $G$ is...
Uploaded on: December 3, 2022 -
2011 (v1)Journal article
{Recently Hansen and Vukicevic proved that the inequality $M_1/n \leq M_2/m$, where $M_1$ and $M_2$ are the first and second Zagreb indices, holds for chemical graphs, and Vukicevic and Graovac proved that this also holds for trees. In both works is given a distinct counterexample for which this inequality is false in general. Here, we present...
Uploaded on: December 3, 2022 -
2015 (v1)Journal article
The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best known theoretical algorithm computing this parameter...
Uploaded on: March 25, 2023 -
September 25, 2012 (v1)Report
Let G be a connected graph, and let d(a, b) denotes the shortest path distance between vertices a and b of G. The graph G is δ-hyperbolic if for any vertices a, b, c, d of G, the two largest of the three sums S1 = d(a,b) + d(c,d), S2 = d(a,c) + d(b,d), and S3 = d(a,d) + d(b,c) differ by at most 2δ. This can be determined in time O(n^4) which...
Uploaded on: December 3, 2022 -
February 2016 (v1)Report
We continue the study, initiated in INRIA research report RR-8867, of the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let E be the following set of properties of digraphs: E ={strongly con- nected, connected, minimum...
Uploaded on: February 28, 2023 -
August 2016 (v1)Journal article
We continue the study, initiated in [3], of the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let EE be the following set of properties of digraphs: E=E={strongly connected, connected, minimum out-degree at least 1, minimum...
Uploaded on: February 28, 2023 -
2012 (v1)Journal article
A good edge-labelling of a graph G is a labelling of its edges such that, for any ordered pair of vertices (x, y), there do not exist two paths from x to y with increasing labels. This notion was introduced in [2] to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of...
Uploaded on: December 3, 2022 -
November 3, 2009 (v1)Conference paper
A good edge-labelling of a graph G is a labelling of its edges such that for any two distinct vertices u, v, there is at most one (u, v)-path with non-decreasing labels. This notion was introduced in [3] to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of graphs that...
Uploaded on: December 4, 2022 -
2017 (v1)Journal article
Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we...
Uploaded on: February 28, 2023 -
November 2017 (v1)Journal article
A (k 1 + k 2)-bispindle is the union of k 1 (x, y)-dipaths and k 2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (2 + 0)-bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We...
Uploaded on: February 28, 2023 -
April 30, 2018 (v1)Journal article
An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number...
Uploaded on: December 4, 2022 -
February 2016 (v1)Report
An {\it oriented cycle} is an orientation of a undirected cycle.We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number.In contrast, we show that for any $C$ is a cycle with two blocks, every strongly connected digraph with sufficiently large...
Uploaded on: February 28, 2023 -
June 8, 2018 (v1)Journal article
A (k1 + k2)-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (1, 1)- bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We...
Uploaded on: December 4, 2022 -
2009 (v1)Report
A {\em good edge-labelling} of a graph $G$ is a labelling of its edges such that, for any ordered pair of vertices $(x,y)$, there do not exist two paths from $x$ to $y$ with increasing labels. This notion was introduced in~\cite{BCP} to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at...
Uploaded on: February 22, 2023 -
November 7, 2016 (v1)Conference paper
Extended Abstract The chromatic number χ(D) of a digraph D is the chromatic number of its underlying graph. An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that...
Uploaded on: February 28, 2023