Acyclic improper choosability of graphs |
| |
| Institution: | 1. Faculty of Informatics, Masaryk University, Botanická 68a, 602 00 Brno, Czech Republic;2. Theoretical Computer Science, RWTH Aachen, Ahornstraße 55, 52056 Aachen, Germany;1. ESSEC Business School, Paris, France;2. Bogazici University, Istanbul, Turkey;3. PSL, Université Paris-Dauphine, 75775 Paris Cedex 16, France;4. CNRS, LAMSADE UMR 7243, France;5. CEREGMIA, University of Antilles-Guyane, Schoelcher, Martinique, France;1. Department of Mathematics and Statistics, McGill University, Montréal, QC, Canada;2. Department of Mathematics, Zhejiang Normal University, Jinhua, Zhejiang Province, 321004, China;3. Department of Mathematics, University of Illinois, Urbana, IL, 61801, USA;4. Pacific Institute of Mathematical Sciences, Department of Mathematics, Simon Fraser University, Burnaby, B.C., Canada V5A1S6;1. Department of Pharmaceutical Sciences, College of Pharmacy, University of Michigan, Ann Arbor, MI, 48109, USA;2. Translational Development and Clinical Pharmacology, Bristol Meyer Squibb Company, Summit, NJ, 07920, USA;1. Depto. de Matemática, FCEIA, Universidad Nacional de Rosario, Argentina;2. CONICET, Argentina |
| |
| Abstract: | We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically (3, 1)*-choosable (i.e. they are acyclically 3-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically (2, 5)*-choosable (i.e. they are acyclically 2-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
