Publication

(p,q) - Choosability of Grid Graphs

Dominique de Werra
2012

Résumé

A bipartite graph G = (V1; V2;E) is said (p; q)-choosable with k colors if, by assigning a list L f1; : : : ; kg of size p to each vertex of V1 and a list L f1; : : : ; kg of size q to each vertex of V2, the related k-list-coloring instance is always satisfiable (i.e. there is a k-list-coloring respecting the lists). We characterize the cases (p; q) for which grid graphs are (p; q)- choosable and, if not, we give the complexity of the related k-list-colorability problem. Results show that only one case is difficult, namely (p; q) = (2; 3) and k 4. As a corollary we get that list-coloring is NP-hard on grids

Source officielle

https://infoscience.epfl.ch/entities/publication/c621e5ca-18a2-4ee5-bc4a-9a47cb72f805

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

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dominique de Werra
2012

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/c621e5ca-18a2-4ee5-bc4a-9a47cb72f805

À propos de ce résultat

Concepts associés (31)

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

List edge-coloring

In mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color. A graph G is k-edge-choosable if every instance of list edge-coloring that has G as its underlying graph and that provides at least k allowed colors for each edge of G has a proper coloring.

Afficher plus

Publications associées (3)

(p,q) - Choosability of Grid Graphs

Chattez avec Graph Search

Partitioning Complete Geometric Graphs on Dense Point Sets Into Plane Subgraphs

Graph Laplacians for Rotation Equivariant Convolutional Neural Networks

Perfect Simulation and Stationarity of a Class of Mobility Models