List Colouring Trees in Logarithmic Space

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We show that List Colouring can be solved on n-vertex trees by a deterministic Turing machine using O(log n) bits on the worktape. Given an n-vertex graph G = (V,E) and a list L(v) ⊆ {1, . . . , n} of available colours for each v ∈ V , a list colouring for G is a proper colouring c such that c(v) ∈ L(v) for all v.

Original languageEnglish
Title of host publication30th Annual European Symposium on Algorithms, ESA 2022
EditorsShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages24:1-24:15
Number of pages15
ISBN (Electronic)9783959772471
ISBN (Print)9783959772471
DOIs
Publication statusPublished - 1 Sept 2022
Event30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, Germany
Duration: 5 Sept 20229 Sept 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume244
ISSN (Print)1868-8969

Conference

Conference30th Annual European Symposium on Algorithms, ESA 2022
Country/TerritoryGermany
CityBerlin/Potsdam
Period5/09/229/09/22

Bibliographical note

Funding Information:
Funding Carla Groenland: Supported by the project CRACKNP that has received funding from the European Research Council (grant agreement No 853234).

Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Funding

Funding Carla Groenland: Supported by the project CRACKNP that has received funding from the European Research Council (grant agreement No 853234).

Keywords

  • graph algorithms
  • List colouring
  • logspace
  • space complexity
  • treepartition-width
  • trees

Fingerprint

Dive into the research topics of 'List Colouring Trees in Logarithmic Space'. Together they form a unique fingerprint.

Cite this