liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A note on adaptable choosability and choosability with separation of planar graphs
Linköping University, Department of Mathematics, Algebra, Geometry and Discrete Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Algebra, Geometry and Discrete Mathematics. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-1143-2496
LaBRI, University of Bordeaux, France.
2021 (English)In: Journal of Combinatorial Mathematics and Combinatorial Computing, ISSN 0835-3026, Vol. 116, p. 101-109Article in journal (Refereed) Published
Abstract [en]

Let F be a (possibly improper) edge-coloring of a graph G; a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |L(v)| ≥ k for all v, and any edge-coloring F of G, G admits a coloring c adapted to F where c(v) ∈ L(v) for all v, then G is said to be adaptably k-choosable. A (k, d)-list assignment for a graph G is a map that assigns to each vertex v a list L(v) of at least k colors such that |L(x) ∩ L(y)\ ≤ d whenever x and y are adjacent. A graph is (k, d)-choosable if for every (k, d)-list assignment L there is an L-coloring of G. It has been conjectured that planar graphs are (3, l)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since (k, l)-choosability is a special case of adaptable k-choosablity, this implies that a planar graph satisfying these conditions is (3,1)-choosable. 

Place, publisher, year, edition, pages
Charles Babbage Research Centre , 2021. Vol. 116, p. 101-109
Keywords [en]
Coloring, Graphic methods, Choosability, Choosable, Edge coloring, Graph G, List assignment, Planar graph, Vertex coloring, Graph theory, Adaptable choosability, Choosability with separation, List coloring
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-188195Scopus ID: 2-s2.0-85112564602OAI: oai:DiVA.org:liu-188195DiVA, id: diva2:1693154
Note

Funding agencies:Carl Johan Casselgren was supported by a grant from the Swedish Research Council (2017-05077). André Raspaud was partially supported by the ANR project HOSIGRA (ANR- 17-CE40-0022)

Available from: 2022-09-05 Created: 2022-09-05 Last updated: 2022-12-21

Open Access in DiVA

No full text in DiVA

Scopus

Authority records

Casselgren, Carl JohanGranholm, Jonas

Search in DiVA

By author/editor
Casselgren, Carl JohanGranholm, Jonas
By organisation
Algebra, Geometry and Discrete MathematicsFaculty of Science & Engineering
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 91 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf