2026-10-02T08:23:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25563 2026-09-23T23:44:07Z ddc:004 open_access

List Coloring Ordered Graphs with Forbidden Induced Subgraphs Piecyk, Marta Rzążewski, Paweł coloring ordered graphs forbidden induced subgraphs In the List k-Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of {1,…,k}. We need to decide if G admits a proper coloring, where every vertex receives a color from its list. The complexity of the problem in classes defined by forbidding induced subgraphs is a widely studied topic in algorithmic graph theory. Recently, Hajebi, Li, and Spirkl [SIAM J. Discr. Math. 38 (2024)] initiated the study of List 3-Coloring in ordered graphs, i.e., graphs with fixed linear ordering of vertices. Forbidding ordered induced subgraphs allows us to investigate the boundary of tractability more closely. We continue this direction of research, focusing mostly on the case of List 4-Coloring. We present several algorithmic and hardness results, which altogether provide an almost complete dichotomy for classes defined by forbidding one fixed ordered graph: our investigations leave one minimal open case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marta Piecyk and Paweł Rzążewski 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.74 urn:nbn:de:0030-drops-255634 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.74 eng https://creativecommons.org/licenses/by/4.0/legalcode