Injective choosability of planar graphs of girth five and six
Injective choosability of planar graphs of girth five and six
复制标题
周长五和六的平面图的内射可选择性
DOI：
10.1016/j.disc.2011.10.029
复制
发表时间：
2012-03
影响因子：
0.8
通讯作者：
许宝刚
中科院分区：
文献类型：
--
作者：
李锐;许宝刚
图G的内射k染色是对V(G)的k种颜色的分配，使得有一个共同邻居的顶点得到不同的颜色。研究了平面图的单射着色的列表形式。设χil(G)和mad(G)分别为G的内射可选择性数和最大平均度。证明(1)对于每一个图G，当mad(G)<103时，如果Δ(G)≥30,χil(G)≤Δ(G)+4(这有条件地改进了Doyon et al.（2010)[9]和Lužar et al.(2009)[11]的一些结果），如果Δ(G)≥18,χil(G)≤Δ(G)+5，如果Δ(G)≥14,χil(G)≤Δ(G)+6；(2)如果mad(G)<3且Δ(G)≥12,χil(G)≤Δ(G)+2（这有条件地改进了Doyon et al.(2010)[9]的结果）。
An injective k-coloring of a graph G is an assignment of k colors to V(G) such that vertices having a common neighbor receive distinct colors. We study the list version of injective colorings of planar graphs. Let χil(G) and mad(G) be the injective choosability number and the maximum average degree of G, respectively. It is proved that (1) for each graph G with mad(G)<103, χil(G)≤Δ(G)+4 if Δ(G)≥30 (this conditionally improves some results of Doyon et al. (2010) [9] and Lužar et al. (2009) [11]), χil(G)≤Δ(G)+5 if Δ(G)≥18, and χil(G)≤Δ(G)+6 if Δ(G)≥14; (2) χil(G)≤Δ(G)+2 if mad(G)<3 and Δ(G)≥12 (this conditionally improves a result of Doyon et al. (2010) [9]).
登录
查看更多内容
DOI：
10.1016/j.disc.2009.06.029
发表时间：
2009-12
期刊：
Discret. Math.
影响因子：
--
作者：
O. Borodin;A. Ivanova
通讯作者：
O. Borodin;A. Ivanova
DOI：
10.1016/j.tcs.2021.01.007
发表时间：
2021-02
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Y. Bu;Chentao Qi;Junlei Zhu;Ting Xu
通讯作者：
Y. Bu;Chentao Qi;Junlei Zhu;Ting Xu
DOI：
10.1057/jors.1977.45
发表时间：
1978-03
期刊：
--
影响因子：
--
作者：
E. Lloyd;J. Bondy;U. Murty
通讯作者：
E. Lloyd;J. Bondy;U. Murty
影响因子：
0.8
作者：
Borodin, O. V.;Ivanova, A. O.
通讯作者：
Ivanova, A. O.
DOI：
10.1016/j.disc.2009.04.020
发表时间：
2010-02
期刊：
Discret. Math.
影响因子：
--
作者：
A. Doyon;G. Hahn;A. Raspaud
通讯作者：
A. Doyon;G. Hahn;A. Raspaud