A new variation of the coloring problem, mu-coloring, is defined in this paper. A coloring of a graph G = (V,E) is a function f: V -> N such that f(v) is different from f(w) if v is adjacent to w. Given a graph G = (V,E) ...

Coloring problems in graphs have been used to model a wide range of real applications. In particular, the List Coloring Problem generalizes the well-known Graph Coloring Problem for which many exact algorithms have been ...

In this paper we present a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes ...

It is shown that Halin graphs are -edge-choosable and that graphs of tree-width 3 are -edge-choosable and -total-colourable.

We prove that the list chromatic index of a graph of maximum degree Delta and treewidth <= root 2 Delta -3 is Delta; and that the total chromatic number of a graph of maximum degree and treewidth <= Delta/3+1 is Delta+1. ...

We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a ...

Colored range queries are a well-studied topic in computational geometry and database research that, in the past decade, have found exciting applications in information retrieval. In this paper, we give improved time and ...

A biclique of a graph G is an induced complete bipartite graph. A star of G is a biclique contained in the closed neighborhood of a vertex. A star (biclique) k-coloring of G is a k-coloring of G that contains no monochromatic ...