On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9
| Autor: | Yingcai Sun, Min Chen, Yanfang He |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics Chordal graph 0202 electrical engineering electronic engineering information engineering symbols Discrete Mathematics and Combinatorics Acyclic coloring Mathematics |
| Zdroj: | Discrete Mathematics. 344:112476 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2021.112476 |
| Popis: | Let G = ( V , E ) . A proper vertex coloring of G is acyclic if there is no bicolored cycle in G. Given a list assignment L = { L ( v ) | v ∈ V } of G, if there exists an acyclic coloring π of G such that π ( v ) ∈ L ( v ) for all v ∈ V , then we say that G is acyclically L-colorable. If G is acyclically L-colorable for any list assignment L with | L ( v ) | ≥ k for all v ∈ V , then G is acyclically k-choosable. It is known that every planar graph without { 4 , i , j } -cycles is acyclically 4-choosable for each pair { i , j } ⊂ { 5 , 6 , 7 , 8 , 9 } and { i , j } ∉ { { 7 , 9 } , { 8 , 9 } } . In this paper, we prove that every planar graph with neither 4-cycles, 7-cycles nor chordal 9-cycles is acyclically 4-choosable. As a corollary, every planar graph without { 4 , 7 , 9 } -cycles is acyclically 4-choosable. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect