没有合适的资源?快使用搜索试试~ 我知道了~
A note on the minimum number of choosability of planar graphs
0 下载量 52 浏览量
2021-02-07
09:20:12
上传
评论
收藏 310KB PDF 举报
温馨提示
The problem of minimum number of choosability of graphs was first introduced.by Vizing. It appears in some practical problems when concerning frequency.assignment. In this paper, we study two important list coloring, list edge coloring and.list total coloring. We prove that χl (G) = Δ and χl (G) = Δ + 1 for planar graphs.with Δ ≥ 8 and without adjacent 4-cycles.
资源推荐
资源详情
资源评论
J Comb Optim (2016) 31:1013–1022
DOI 10.1007/s10878-014-9805-2
A note on the minimum number of choosability
of planar graphs
Huijuan Wang · Lidong Wu · Xin Zhang ·
Weili Wu · Bin Liu
Published online: 17 October 2014
© Springer Science+Business Media New York 2014
Abstract The problem of minimum number of choosability of graphs was first intro-
duced by Vizing. It appears in some practical problems when concerning frequency
assignment. In this paper, we study two important list coloring, list edge coloring and
list t otal coloring. We prove that χ
l
(G) = Δ and χ
l
(G) = Δ + 1 for planar graphs
with Δ ≥ 8 and without adjacent 4-cycles.
Keywords Choosability · Planar graph · Cycle · List edge coloring
H. Wang
College of Mathematics, Qingdao University, Qingdao 266071, China
e-mail: sduwhj@163.com
L. Wu
Department of Computer Science, University of Texas at Tyler, Tyler, TX 75799, USA
e-mail: wu-ld@hotmail.com
X. Zhang
School of Mathematics and Statistics, Xidian University, Xi’an 710071, China
e-mail: xzhang@xidian.edu.cn
W. Wu
College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan 030024,
China
W. Wu
Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA
e-mail: weiliwu@utdallas.edu
B. Liu (
B
)
Department of Mathematics, Ocean University of China, Qingdao 266100, China
e-mail: sduliubin@163.com
123
1014 J Comb Optim (2016) 31:1013–1022
1 Introduction
The theory of graph coloring has important application in combinatorial optimiza-
tion, web design, computer science and so on. Particularly, in files transmission of a
computer network, channel assignment, pattern matching, computation of Hessians
matrix. In this paper, we consider two important coloring, list edge coloring and list
total coloring, which arise in some practical problems concerning frequency assign-
ment. Here are some other interesting colorings, we refer the readers to Angelini and
Frati (2012); Bessy and Havet (2013); Du et al. (2004); Garg et al. (1996); Li et al.
(2013); Wang et al. (2014b,a)etc.
All graphs considered in this paper are simple. Let G be a planar graph and has
embedded in the plane. We use V (G), E(G), F(G), Δ(G) and δ(G) to denote the
vertex set, the edge set, the face set, the maximum degree and the minimum degree
of G, respectively. For a vertex v of G,thedegree d(v) denote the number of edges
incident with v, and for a face f of G,thedegree d( f ) denote the length of the boundary
walk of f . Denote by k-vertex the vertex of degree k,byk
−
-vertex the vertex of degree
at most k,byk
+
-vertex the vertex of degree at least k. If two cycles share at l east one
edge, we call them adjacent.Weusen
k
(v), f
k
(v) and n
k
( f ) to denote the number of
k-vertices adjacent to the vertex v, the number of k-faces incident with the vertex v,
and the number of k-vertices incident with the face f , respectively. In the following,
we shall introduce the notations of list total coloring and list edge coloring.
The problem of minimum number of choosability of graphs was first introduced
by Vizing (1976). Firstly, list total coloring is a type of coloring that combines list
coloring with total coloring. It is a choice of a color for each vertex or each edge, from
its list of allowed colors; the coloring is proper if no two adjacent or incident elements
receive the same color. Specifically, a mapping L is called to be a total assignment
for a graph G if it assigns a list L(x) of possible colors for each element x ∈ V ∪ E .
If G has a total coloring ϕ such that ϕ(x) ∈ L(x) for all x ∈ V ∪ E, and no two
adjacent or incident elements receive the same color, then we say that ϕ is a total-L
-coloring of G or G is total-L -colorable. A graph G is called total-k -choosable if it is
total-L-colorable for every total assignment L satisfying |L(x)|≥k for each element
x ∈ V ∪ E .Thelist total chromatic number χ
l
(G) of G is the smallest integer k
such that G is total-k-choosable. Similarly, the list edge chromatic number χ
l
(G) of
G can be defined in terms of coloring the edges alone. The ordinary edge chromatic
number of G are denoted by χ
(G). Obviously, it holds that χ
l
(G) ≥ χ
(G) ≥ Δ and
χ
l
(G) ≥ χ
(G) ≥ Δ + 1.
As far as list edge colorings and list total colorings are widely studied, quite a few
interesting results have been obtained in recent years. Firstly, we introduce a famous
conjecture.
Conjecture 1 (List Coloring Conjecture) For any graph G,
(a) χ
l
(G) = χ
(G);
(b) χ
l
(G) = χ
(G).
Part (a) of Conjecture 1 was formulated independently by a number of people,
including Vizing, Gupta, Albertson and Collins, Bollobás and Harris (see Hägkvist
123
剩余9页未读,继续阅读
资源评论
weixin_38548434
- 粉丝: 3
- 资源: 945
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- lsb-release,安装磐维数据库,安装oracle数据库等常用的依赖包
- redhat-lsb-core,安装磐维数据库,安装oracle数据库等常用的依赖包
- 丹佛丝堆垛机变频器参数配置起升、运行、货叉
- JSP学生学籍管理系统(源代码+论文+开题报告+外文翻译+答辩PPT).rar
- jsp医院病区管理系统(论文+中期检查表+任务书+综合材料).rar
- jsp研究生党建管理系统pc-毕业设计.rar
- JSP在线考试系统的设计与实现(源代码+论文).rar
- JSP在线CD销售系统(论文).rar
- jSP在线教学质量评价系统的设计与实现(源代码+论文).rar
- JSP自动排课管理系统(源代码+论文+开题报告).rar
- JSP在线学习系统设计(源代码+论文).rar
- JSP作业管理系统(源代码+论文).rar
- JSP自动排课系统(源代码+论文+开题报告).rar
- lerx2_utf8_v2_beta2_20121214.rar
- putty,linux客户端工具
- 提高Windows 11文件资源管理器显示文件夹大小功能
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功