LINHARES SALES , Claudia

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

In this paper, we summarize some problems arising in telecommunication networks which have been studied in the scope of the cooperation between our teams ParGO (UFC) and Mascotte (INRIA). We also present their modeling by graph coloring problems and some partial results we have ob- tained.

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

In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves the proportion given by the weights associated to each edge. If such colouring exists, we want to find one using a minimum number of colours. We...

A given k-coloring c of a graph G = (V,E) is a b-coloring if for every color class ci, 1 ≤ i ≤ k, there is a vertex colored i whose neighborhood intersects every other color class cj of c. The b-chromatic number of G is the greatest integer k such that G admits a b-coloring with k colors. A graph G is tight if it has exactly m(G) vertices of...

The Grundy number of a graph G, denoted by Gamma(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of...

A coloring c of a graph G = (V,E) is a b-coloring if in every color class there is a vertex whose neighborhood intersects every other color classes. The b-chromatic number of G, denoted χb(G), is the greatest integer k such that G admits a b-coloring with k colors. A graph G is tight if it has exactly m(G) vertices of degree m(G) − 1, where...

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

We study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. This problem is motivated by a frequency allocation problem. We propose approximation algorithms to compute such colouring.

We study a weighted improper colouring problem motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most k (the case k = 0 corresponds to a proper coloring). The objective is...

The Grundy number of a graph G is the largest k such that G has a greedy k- colouring, that is, a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we give new bounds on the Grundy number of the product of two graphs.

The Grundy number of a graph G is the largest k such that G has a greedy k-colouring, that is, a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we give new bounds on the Grundy number of the product of two graphs.

Given a graph G = (V;E), a greedy coloring of G is a proper coloring such that, for each two colors i < j, every vertex of V(G) colored j has a neighbor with color i. The greatest k such that G has a greedy coloring with k colors is the Grundy number of G. A b-coloring of G is a proper coloring such that every color class contains a vertex...

Let $f(k)$ be the smallest integer such that every $f(k)$-chromatic digraph contains every oriented tree of order $k$. Burr proved $f(k)\leq (k-1)^2$ in general, and he conjectured $f(k)=2k-2$. Burr also proved that every $(8k-7)$-chromatic digraph contains every antidirected tree. We improve both of Burr's bounds. We show that $f(k)\leq...

Given a graph G = (V;E), a greedy coloring of G is a proper coloring such that, for each two colors i < j, every vertex of V(G) colored j has a neighbor with color i. The greatest k such that G has a greedy coloring with k colors is the Grundy number of G. A b-coloring of G is a proper coloring such that every color class contains a vertex...

Let f (k) be the smallest integer such that every f (k)-chromatic digraph contains every oriented tree of order k. Burr proved that f (k) ≤ (k − 1)^2 and conjectured f (k) = 2n − 2. In this paper, we give some sufficient conditions for an n-chromatic digraphs to contains some oriented tree. In particular, we show that every acyclic n-chromatic...

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of P4-tidy graphs and (q,q − 4)-graphs, for every fixed q. These classes include cographs, P4-sparse and P4-lite graphs. We also obtain a polynomial time algorithm to determine the Grundy...