ARAUJO , Julio

In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the rst and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of...

A coloração ótima dos vértices de um grafo é um dos problemas mais estudados em teoria dos grafos devido ao número de aplicações que o problema modela e à dificuldade inerente ao problema, pois determinar o número cromático de um grafo é NP-difícil. O Teorema de Hajós clássico [Hajós, 1961] mostra uma condição necessária e suficiente para que...

The Hajós' Theorem (Wiss Z Martin Luther Univ Math-Natur Reihe, 10, pp 116-117, 1961) shows a necessary and sufficient condition for the chromatic number of a given graph $G$ to be at least $k$ : $G$ must contain a $k$ -constructible subgraph. A graph is $k$ -constructible if it can be obtained from a complete graph of order $k$ by successively...

Given an undirected graph G = (V, E) and a weight function w : V → R+, a vertex coloring of G is a partition of V into independent sets, or color classes. The weight of a vertex coloring of G is defined as the sum of the weights of its color classes, where the weight of a color class is the weight of a heaviest vertex belonging to it. In the...

The Grundy number of a graph G is the largest number of colors used by any execution of the greedy algorithm to color G. The problem of determining the Grundy number of G is polynomial if G is a P4-free graph and NP-hard if G is a P5-free graph. In this article, we define a new class of graphs, the fat-extended P4-laden graphs, and we show a...

In this article, we define a new class of graphs, the fat-extended P4 -laden graphs, and we show a polynomial time algorithm to determine the Grundy number of the graphs in this class. This result implies that the Grundy number can be found in polynomial time for any graph of the following classes: P4 -reducible, extended P4 -reducible, P4...

Distributed or peer-to-peer storage solutions rely on the introduction of redundant data to be fault-tolerant and to achieve high reliability. One way to introduce redundancy is by simple replication. This strategy allows an easy and fast access to data, and a good bandwidth e ciency to repair the missing redundancy when a peer leaves or fails...

A function f:V(G)→{1,…,k}f:V(G)→{1,…,k} is a (proper) k-colouring of G if |f(u)−f(v)|≥1|f(u)−f(v)|≥1, for every edge uv∈E(G)uv∈E(G). The chromatic number χ(G)χ(G) is the smallest integer k for which there exists a proper k-colouring of G.Given a graph G and a subgraph H of G, a circular q-backbone k-colouring c of (G, H) is a k-colouring of...

Grafos mistos são estruturas matemáticas que mesclam características de grafos direcionados e não-direcionados. Formalmente, um grafo misto pode ser definido por uma tripla GM = (V, A, E), onde V , A e E representam, respectivamente, um conjunto de vértices, de arcos e de arestas. Uma k-coloração mista de GM = (V, A, E) é função c : V → {0, . ....

Une fonction $f: V(G)\to \{1,\ldots,k\}$ est une $k$-coloration (propre) de $G$ si $|f (u) - f (v)|\geq 1$, pour toute ar\^ete $uv\in E(G)$. Le {\it nombre chromatique} $\chi(G)$ est le plus petit entier $k$ tel qu'il existe une $k$-coloration propre de $G$.Etant donn\'es un graphe $G$ et un sous-graphe $H$ de $G$, une $k$-coloration...

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a...

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a {\it color}. For a vertex-weighted graph, the {\it weight of a color} is the maximum weight of its vertices. The {\it weight of a coloring} is the sum of the weights of its colors. Guan and Zhu defined the {\it weighted chromatic...

International audience

In this article, we generalize the concepts of Eulerian and Hamiltonian digraphs to directed hypergraphs. A dihypergraph H is a pair (V(H), E(H)), where V(H) is a non-empty set of elements, called vertices, and E(H) is a collection of ordered pairs of subsets of V(H), called hyperarcs. It is Eulerian (resp. Hamiltonian) if there is a dicycle...

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...

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...

Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded...

An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number − → χ (G) of a graph G is the minimum maximum in-degree of a proper orientation of G. In [1], the authors ask whether the proper orientation number of a planar graph is bounded. We prove that every cactus admits a proper...

An orientation of a graph is proper if two adjacent vertices have different indegrees. We prove that every cactus admits a proper orientation with maximum indegree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum indegree less than 7. We also prove that any planar claw-free graph...

In this paper, we study the (geodesic) hull number of graphs. For any two vertices $u,v\in V$ of a connected undirected graph $G=(V,E)$, the closed interval $I[u,v]$ of $u$ and $v$ is the set of vertices that belong to some shortest $(u,v)$-path. For any $S \subseteq V$, let $I[S]= \bigcup_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is...

In this paper, we study the (geodesic) hull number of graphs. For any two vertices $u,v\in V$ of a connected undirected graph $G=(V,E)$, the closed interval $I[u,v]$ of $u$ and $v$ is the set of vertices that belong to some shortest $(u,v)$-path. For any $S \subseteq V$, let $I[S]= \bigcup_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is...

In order to optimize energy efficiency, network operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing the network congestion. In this work, we study...

International audience