Publication

On some coloring problems in grids

Dominique de Werra
2013
Journal Articles

Abstract

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of the bipartition are all of size p and lists in the second part are of size q. In particular, we characterize the complexity of (p, q)-List coloring in grid graphs, showing that the only NP-complete case is (2, 3)-List coloring with k >= 4 colors. We also show that Precoloring extension with 3 colors is NP-complete in subgrids. (C) 2012 Elsevier B.V. All rights reserved.

Official source

https://infoscience.epfl.ch/entities/publication/a103ef16-9572-4af3-a3af-8eddc868a625

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Dominique de Werra
2013
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/a103ef16-9572-4af3-a3af-8eddc868a625

About this result

Related concepts (32)

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Edge coloring

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.

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.

Related publications (32)

On some coloring problems in grids

Chat with Graph Search

The Power of Two Matrices in Spectral Algorithms for Community Recovery

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem