列表双临界图（英文）

李中华; 吴宝音都仍; 安新慧; 刘凤霞

doi:10.13568/j.cnki.651094.2018.01.001

您当前的位置：

首页 >

文章列表页 >

列表双临界图（英文）

研究精粹 | 更新时间：2026-01-21

- 列表双临界图（英文）
- 列表双临界图（英文）
- 新疆大学学报（自然科学版中英文） 2018年35卷第1期页码：1-3
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  Research supported by National Natural Science Foundation of China(11161046,11571294)
- DOI：10.13568/j.cnki.651094.2018.01.001
  中图分类号： O157.5
- 纸质出版：2018
- 稿件说明：
移动端阅览
[1]李中华,吴宝音都仍,安新慧,等.列表双临界图（英文）[J],2018,35(01):1-3.
[1]李中华,吴宝音都仍,安新慧,等.列表双临界图（英文）[J],2018,35(01):1-3. DOI： 10.13568/j.cnki.651094.2018.01.001.

DOI：10.13568/j.cnki.651094.2018.01.001.

摘要

G是k-可着色的连通图

如果对于G中的所有边uv

都有G-u-v是(k-2)-可着色的

则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图

如果G中包含多对不相邻的边

并且对于任意一对不相邻的边e1

都有χ(G-e1-e2)=χ(G)-2

其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中

对于任意的两个点u

v∈V(G)

如果ch(G-u-v)=ch(G)-2

则图G是完全图

其中ch(G)表示G的选择数

还证明了完全图是唯一的列表双临界图.

Abstract

A connected k-chromatic graph G is double-critical if for all edges uv of G the graph G-u-v is(k-2)-colorable. A long-standing conjecture

due to Erd o?s and Lova′sz[1]

states that the complete graphs are the only double-critical graphs. A connected graph G is called edge double-critical if it contains some pairs of nonadjacent edges

and χ(G-e1-e2) =χ(G)-2 for any two nonadjacent edges e1

e2∈ E(G)

where χ(G) denotes the chromatic number of G. Kawarabayashi et al.[2]and later

Lattanzio[3]proved that the complete graphs are the only edge double-critical graphs. In this note

we show that for a graph G

if ch(G-u-v) = ch(G)-2 for any vertices u

v ∈ V(G)

then G is a complete graph

where ch(G) denotes the choice number of G. We also prove that the complete graphs are the only edge list double-critical graphs.

关键词

Keywords

references

Erd o?s P.In Theory of Graphs[M].New York:Academic Press,1968:361.

Kawarabayashi K,Pedersen A S,Toft B.Double-critical graphs and complete minors[J].Electron J Combin,2010,17:1-27.

Lattanzio J J.Edge double-critical graphs[J].J Math Stat,2010,6:357-358.

West D B.Introduction to Graph Theory,Second Edition[M].Upper Saddle River:Prentice Hall,NJ,2001.

Stiebitz M.K5is the only double-critical 5-chromatic graph[J].Discrete Math,1987,64:91-93.

Pedersen A S.Contributions to the Theory of Colourings,Graph Minors,and Independent Sets[D].Odense:University of Southern Denmark,2011.

He W,Zhang L,Cranston D W,et al.Choice number of complete multipartite graphs K3*3,2*(k-5),1*2and K4,3*2,2*(k-6),1*3[J].Discrete Math,2008,308:5871-5877.

Ohba K.On chromatic-choosable graphs[J].J Graph Theory,2002,40:130-135.

Shen Y,He W,Wang Y,et al.On choice number of some complete multipartite graphs and Ohba’s conjecture[J].Discrete Math,2008,308:136-143.

Kierstead H A.On the choosability of complete multipartite graphs with part size three[J].Discrete Math,2000,211:255-259.

Erd o?s P,Rubin A L,Taylor H.Choosability in graphs[J].Congr Num,1979,26:125-157.

Gravier S,Maffray F.Graphs whose choice number is equal to their chromatic number[J].J Graph Theory,1998,27:87-97.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

路图P₃(G)的色数(英文)

[2,3]-可选的完全二部图的刻划(英文)

图的色数的一个上界

线团图的一些性质