Anoteontheminimumnumberofchoosabilityofplanargraphs资源-CSDN文库

研究论文

135 浏览量 2021-02-07 09:20:12 上传评论收藏 310KB PDF 举报

资源推荐

资源详情

资源评论

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

Abstract The problem of minimum number of choosability of graphs was ﬁrst 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 χ



(G) = Δ and χ



(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 (

)

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 ﬁles 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

(v), f

(v) and n

( 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 ﬁrst 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. Speciﬁcally, 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 χ



(G) of G is the smallest integer k

such that G is total-k-choosable. Similarly, the list edge chromatic number χ



(G) of

G can be deﬁned in terms of coloring the edges alone. The ordinary edge chromatic

number of G are denoted by χ



(G). Obviously, it holds that χ



(G) ≥ χ



(G) ≥ Δ and



(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) χ



(G) = χ



(G);

(b) χ



(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

A note on the minimum number of choosability of planar graphs

The minimal spectral radius of graphs with a given independence number

基于CORDIC的反正弦和反余弦计算的FPGA实现

BA无标度网络中的SIR模型

使用3DCNN和卷积LSTM进行手势识别学习时空特征

基于三次贝塞尔曲线的类汽车曲率连续路径平滑

基于机器学习的设备剩余寿命预测方法综述

基于维纳过程的退化模型，具有递归过滤算法，可用于估计剩余使用寿命

基于FPGA的奇异值和特征值分解的快速实现。

磁悬浮系统自适应模糊PID控制器的设计

基于BP神经网络的人口预测

两轮平衡车的建模与控制研究

无人机协同目标的多无人机协同搜索方法

基于改进遗传算法的六自由度机器人时间最优轨迹规划

一种基于深度学习的机械臂抓取方法

基于深度神经网络的交通流量预测

一种去除ECG中基线漂移和工频干扰的高效滤波方法

基于稀疏贝叶斯学习的高效DOA估计方法

适用于1-8GHz宽带应用的原始Vivaldi天线

亮度保持和细节增强的红外图像增强方法

一种基于LMS算法的流水线ADC数字校准算法

一种鲁棒的三维点云骨架提取方法

弗兰克（Frank）编码的LFM波形及其在MIMO雷达中的应用

一种新的基于维纳过程的自适应使用寿命剩余寿命预测方法

MUSIC算法中频谱峰值搜索的研究及FPGA实现

室内服务移动机器人的ORB-SLAM定位导航方法

最新资源