LIPIcs.ISAAC.2020.31.pdf
- Filesize: 474 kB
- 15 pages
Document
Flexible List Colorings in Graphs with Special Degeneracy Conditions
Authors
Peter Bradshaw 
,
Tomáš Masařk ,
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.31
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph coloring
Keywords
- Flexibility
- List Coloring
- Choosability
- Degeneracy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Miklos Biró, Mihály Hujter, and Zsolt Tuza. Precoloring extension. I. interval graphs. Discrete Mathematics, 100(1-3):267-279, May 1992. URL: https://doi.org/10.1016/0012-365x(92)90646-w.
- Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, December 1996. URL: https://doi.org/10.1137/s0097539793251219.
- Hans L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Graph-Theoretic Concepts in Computer Science, pages 1-14. Springer Berlin Heidelberg, 2006. URL: https://doi.org/10.1007/11917496_1.
- Paul Bonsma and Florian Zickfeld. Improved bounds for spanning trees with many leaves. Discrete Mathematics, 312(6):1178-1194, 2012. URL: https://doi.org/10.1016/j.disc.2011.11.043.
- Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho. Flexible list colorings in graphs with special degeneracy conditions, 2020. URL: http://arxiv.org/abs/2006.15837.
- Hojin Choi and Young Soo Kwon. On t-common list-colorings. Electronic Journal of Combinatorics, 24(3):Paper No. 3.32, 10, 2017. URL: https://doi.org/10.37236/6738.
- Ilkyoo Choi, Felix C. Clemen, Michael Ferrara, Paul Horn, Fuhong Ma, and Tomáš Masařík. Flexibility of planar graphs - sharpening the tools to get lists of size four, 2020. URL: http://arxiv.org/abs/2004.10917.
- Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, fifth edition, 2017. URL: https://doi.org/10.1007/978-3-662-53622-3.
- Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, and Ondřej Pangrác. Flexibility of planar graphs of girth at least six. Journal of Graph Theory, 95(3):457-466, November 2020. URL: https://doi.org/10.1002/jgt.22567.
- Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, and Ondřej Pangrác. Flexibility of triangle-free planar graphs. Journal of Graph Theory, October 2020. URL: https://doi.org/10.1002/jgt.22634.
- Zdeněk Dvořák, Sergey Norin, and Luke Postle. List coloring with requests. Journal of Graph Theory, 92(3):191-206, 2019. URL: https://doi.org/10.1002/jgt.22447.
- Yoshimi Egawa, Haruhide Matsuda, Tomoki Yamashita, and Kiyoshi Yoshimoto. On a spanning tree with specified leaves. Graphs and Combinatorics, 24(1):13-18, 2008. URL: https://doi.org/10.1007/s00373-007-0768-2.
- Paul Erdős and András Hajnal. On chromatic number of graphs and set-systems. Acta Mathematica. Academiae Scientiarum Hungaricae, 17:61-99, 1966. URL: https://doi.org/10.1007/BF02020444.
-
Paul Erdős, Arthur L. Rubin, and Herbert Taylor. Choosability in graphs. In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pages 125-157. Utilitas Math., Winnipeg, Man., 1980.
- Jerrold R. Griggs, Daniel J. Kleitman, and Aditya Shastri. Spanning trees with many leaves in cubic graphs. Journal of Graph Theory, 13(6):669-695, 1989. URL: https://doi.org/10.1002/jgt.3190130604.
- Mihály Hujter and Zsolt Tuza. Precoloring extension III: Classes of perfect graphs. Combinatorics, Probability and Computing, 5(1):35-56, March 1996. URL: https://doi.org/10.1017/s0963548300001826.
- Bernard Lidický, Tomáš Masařík, Kyle Murphy, and Shira Zerbib. On weak flexibility in planar graphs, 2020. URL: http://arxiv.org/abs/2009.07932.
- Dániel Marx. Precoloring extension on unit interval graphs. Discrete Applied Mathematics, 154(6):995-1002, April 2006. URL: https://doi.org/10.1016/j.dam.2005.10.008.
- Tomáš Masařík. Flexibility of planar graphs without 4-cycles. Acta Mathematica Universitatis Comenianae, 88(3):935-940, August 2019. URL: http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1182.
- Zsolt Tuza and Margit Voigt. A note on planar 5-list colouring: non-extendability at distance 4. Discrete Mathematics, 251(1-3):169-172, May 2002. URL: https://doi.org/10.1016/s0012-365x(01)00338-7.
- Donglei Yang and Fan Yang. Flexibility of planar graphs without C₄ and C₅, 2020. URL: http://arxiv.org/abs/2006.05243.
- Xuding Zhu. A refinement of choosability of graphs. Journal of Combinatorial Theory. Series B, 141:143-164, 2020. URL: https://doi.org/10.1016/j.jctb.2019.07.006.