• English
    • Türkçe
  • English 
    • English
    • Türkçe
  • Login
View Item 
  •   DSpace Home
  • Araştırma Çıktıları / Scopus
  • Araştırma Çıktıları / Scopus
  • View Item
  •   DSpace Home
  • Araştırma Çıktıları / Scopus
  • Araştırma Çıktıları / Scopus
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

On list k-coloring convex bipartite graphs

Thumbnail
Date
2021
Author
Diaz, Josep
Diner, Öznur Yaşar
Serna, Maria
Oriol, Serra
Abstract
List k-Coloring (Lik-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1, 2, …, k}. The problem is known to be NP-hard even for k = 3 within the class of 3-regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of Li 3-Col in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that Lik-Col is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright et al. (SIAM J Discrete Math 28(4):1675–1685, 2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the Lik-Col in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LiH-Col problem on convex bipartite graphs.

Source

AIRO Springer Series

Volume

5

Pages

15-26

URI

https://hdl.handle.net/20.500.12469/4071

Collections

  • Araştırma Çıktıları / Scopus [1565]

Keywords

Biconvex bipartite graphs
Convex bipartite
List coloring

Share


DSpace software copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
Theme by 
@mire NV
 

 

Browse

All of DSpaceCommunities & CollectionsBy Issue DateBy AuthorsBy TitlesBy SubjectsBy TypesBy LanguagesBy DepartmentsBy PublishersBy KHAS AuthorsBy Access TypesThis CollectionBy Issue DateBy AuthorsBy TitlesBy SubjectsBy TypesBy LanguagesBy DepartmentsBy PublishersBy KHAS AuthorsBy Access Types

My Account

LoginRegister

Statistics

View Google Analytics Statistics

DSpace software copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
Theme by 
@mire NV