Dynamic choosability of triangle-free graphs and sparse random graphs

DOI10.1002/JGT.22161MaRDI QIDQ4638632zbMATH OpenOpenAlexFDO

Authors Seongmin Ok, Jaehoon Kim

Publication date 27 April 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04492

zbMATH Keywords

dynamic choosabilitydynamic coloringdynamic list coloringstrong coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: The extit{$r$-dynamic choosability} of a graph $G$, written ${mch}_r(G)$, is the least $k$ such that whenever each vertex is assigned a list of at least $k$ colors a proper coloring can be chosen from the lists so that every vertex $v$ has at least $min{d}_G(v),r$ neighbors of distinct colors. Let $mch(G)$ denote the choice number of $G$. In this paper, we prove ${mch}_r(G)leq(1+o(1))mch(G)$ when $fracDelta(G)delta(G)$ is bounded. We also show that there exists a constant $C$ such that for the random graph $G=G(n,p)$ with $frac2n<pleqfrac12$, it holds that ${mch}_2(G)leqmch(G)+C$, asymptotically almost surely. Also if $G$ is triangle-free regualr graph, then ${mch}_2(G)leqmch(G)+86$ holds.

Recommendations

• List coloring of random and pseudo-random graphs
• On \(r\)-dynamic coloring of graphs
• List \(r\)-dynamic coloring of sparse graphs
• Optimal \(r\)-dynamic coloring of sparse graphs
• The Choice Number of Dense Random Graphs

Cited in

(2)

• List 3-dynamic coloring of graphs with small maximum average degree
• Optimal secret share distribution in degree splitting communication networks

This page was built for publication: Dynamic choosability of triangle-free graphs and sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638632)