A $$(3,1)^{*}$$ ( 3, 1 ) ∗ -choosable theorem on planar graphs

Min Chen (), André Raspaud () and Weifan Wang ()
Additional contact information
Min Chen: Zhejiang Normal University
André Raspaud: LaBRI UMR CNRS 5800, Universite Bordeaux I
Weifan Wang: Zhejiang Normal University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 3, No 18, 927-940

Abstract: Abstract A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex $$v\in V(G)$$ v ∈ V ( G ) . An $$(L,d)^*$$ ( L , d ) ∗ -coloring is a mapping $$\pi $$ π that assigns a color $$\pi (v)\in L(v)$$ π ( v ) ∈ L ( v ) to each vertex $$v\in V(G)$$ v ∈ V ( G ) so that at most d neighbors of v receive color $$\pi (v)$$ π ( v ) . A graph G is said to be $$(k,d)^*$$ ( k , d ) ∗ -choosable if it admits an $$(L,d)^*$$ ( L , d ) ∗ -coloring for every list assignment L with $$|L(v)|\ge k$$ | L ( v ) | ≥ k for all $$v\in V(G)$$ v ∈ V ( G ) . In this paper, we prove that every planar graph with neither adjacent triangles nor 6-cycles is $$(3,1)^*$$ ( 3 , 1 ) ∗ -choosable. This is a partial answer to a question of Xu and Zhang (Discret Appl Math 155:74–78, 2007) that every planar graph without adjacent triangles is $$(3,1)^*$$ ( 3 , 1 ) ∗ -choosable. Also, this improves a result in Lih et al. (Appl Math Lett 14:269–273, 2001) which says that every planar graph without 4- and 6-cycles is $$(3,1)^*$$ ( 3 , 1 ) ∗ -choosable.

Keywords: Planar graphs; Improper choosability; Cycle (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9913-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:3:d:10.1007_s10878-015-9913-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9913-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().