Coloration de liste

Résumé

vignette|301x301px| Une instance de coloration de liste du graphe biparti complet K 3,27 avec trois couleurs par sommet. Pour tout choix de couleurs des trois sommets centraux, l'un des 27 sommets extérieurs ne peut être coloré, ce qui montre que le nombre chromatique de liste de K 3,27 est au moins quatre. En théorie des graphes, la coloration de liste est une coloration des sommets d'un graphe où la couleur de chaque sommet est restreinte à une liste de couleurs autorisées. Elle a été étudiée pour la première fois dans les années 1970 dans des articles indépendants par Vadim G. Vizing et par Paul Erdős, et Herbert Taylor . Définition Étant donné un graphe G et un ensemble L(s) de couleurs pour chaque sommet s (appelé sa liste), une coloration de liste est une fonction qui assigne à chaque sommet s à une couleur de la liste L(s). Comme pour la coloration usuelle des graphes, une coloration de liste est généralement supposée propre, ce qui signifi

Source officielle

https://fr.wikipedia.org/wiki/Coloration_de_liste

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (2)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (4)

Concepts associés

Chargement

Cours associés (2)

Cours associés

Chargement

Séances de cours associées (3)

Séances de cours associées

Chargement

On coloring problems with local constraints

Yuri Faenza

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 subset of vertices colored beforehand), and a problem generalizing both of them, the (γ,μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique-trees of different heights, providing polynomial-time algorithms for the cases that are easy. These results have interesting corollaries. First, one can observe on clique-trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ,μ)-coloring, and list-coloring. Second, clique-trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial-time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ,μ)-coloring is NP-complete. Last, we show that theμ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from Bonomo et al. [F. Bonomo, G. Durán, J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research 169 (1) (2009) 3–16].

Elsevier2012

Chargement

Split-critical and uniquely split-colorable graphs

Dominique de Werra, Tinaz Ekim, Bernard Ries

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic.

2010

Chargement