Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On some coloring problems in grids
 
research article

On some coloring problems in grids

Demange, Marc
•
de Werra, Dominique
2013
Theoretical Computer Science

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.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.tcs.2012.10.046
Web of Science ID

WOS:000315754000002

Author(s)
Demange, Marc
de Werra, Dominique
Date Issued

2013

Published in
Theoretical Computer Science
Volume

472

Issue

11

Start page

9

End page

27

Subjects

List coloring

•

Precoloring extension

•

Grid graphs

•

Complexity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
TRANSP-OR  
Available on Infoscience
January 20, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/99608
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés