DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.31

Flexible List Colorings in Graphs with Special Degeneracy Conditions

Authors: Peter Bradshaw, Tomáš Masařk, and Ladislav Stacho

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract

For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Δ that are ε-flexibly Δ-choosable for some ε = ε(Δ) > 0, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020], and we give conditions for list assignments by which graphs of treewidth k are 1/(k+1)-flexibly (k+1)-choosable. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable. Finally, we introduce a notion of flexible degeneracy, which strengthens flexible choosability, and we show that apart from a well-understood class of exceptions, 3-connected non-regular graphs of maximum degree Δ are flexibly (Δ - 1)-degenerate.

Cite as

Peter Bradshaw, Tomáš Masařk, and Ladislav Stacho. Flexible List Colorings in Graphs with Special Degeneracy Conditions. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bradshaw_et_al:LIPIcs.ISAAC.2020.31,
  author =	{Bradshaw, Peter and Masa\v{r}k, Tom\'{a}\v{s} and Stacho, Ladislav},
  title =	{{Flexible List Colorings in Graphs with Special Degeneracy Conditions}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.31},
  URN =		{urn:nbn:de:0030-drops-133750},
  doi =		{10.4230/LIPIcs.ISAAC.2020.31},
  annote =	{Keywords: Flexibility, List Coloring, Choosability, Degeneracy}
}

Document

DOI: 10.4230/LIPIcs.SOCG.2015.360

Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems

Authors: Ho-Lin Chen, David Doty, Ján Manuch, Arash Rafiey, and Ladislav Stacho

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly and avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

Cite as

Ho-Lin Chen, David Doty, Ján Manuch, Arash Rafiey, and Ladislav Stacho. Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 360-373, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.SOCG.2015.360,
  author =	{Chen, Ho-Lin and Doty, David and Manuch, J\'{a}n and Rafiey, Arash and Stacho, Ladislav},
  title =	{{Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{360--373},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.360},
  URN =		{urn:nbn:de:0030-drops-50935},
  doi =		{10.4230/LIPIcs.SOCG.2015.360},
  annote =	{Keywords: self-assembly, hierarchical, pumping}
}

Search Results

Documents authored by Stacho, Ladislav

Flexible List Colorings in Graphs with Special Degeneracy Conditions

Abstract

Cite as

Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message