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. Conferences, Workshops, Symposiums, and Seminars
  4. (p,q) - Choosability of Grid Graphs
 
conference paper

(p,q) - Choosability of Grid Graphs

Demange, Marc
•
de Werra, D.  
January 30, 2012
Annual International Conference on Computational Mathematics, Computational Geometry & Statistics (CMCGS 2012)
Annual International Conference on Computational Mathematics, Computational Geometry & Statistics (2012(

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

  • Details
  • Metrics
Type
conference paper
DOI
10.5176/2251-1911_cmcgs57
Author(s)
Demange, Marc

École Polytechnique Fédérale de Lausanne

de Werra, D.  

École Polytechnique Fédérale de Lausanne

Date Issued

2012-01-30

Publisher

Global Science and Technology Forum (GSTF)

Published in
Annual International Conference on Computational Mathematics, Computational Geometry & Statistics (CMCGS 2012)
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Event nameEvent acronymEvent placeEvent date
Annual International Conference on Computational Mathematics, Computational Geometry & Statistics (2012(

CMCGS 2012

2012

Available on Infoscience
February 5, 2026
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/258936
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