The chromatic number of the square of a Halin graph with maximum degree five is six

被引：0

作者：

Wang, Yiqiao ^{[1
]}

Hu, Xiaoxue ^{[2
]}

Wang, Weifan ^{[2
]}

机构：

[1] Beijing Univ Chinese Med, Sch Management, Beijing 100029, Peoples R China

[2] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

来源：

ARS COMBINATORIA | 2017年 / 133卷

关键词：

Halin graph; Square; Chromatic number; Maximum degree; DISTANCE; 2; PLANAR GRAPH;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

This article proves that the square of a Halin graph G with Delta = 5 has the chromatic number 6. This gives a positive answer to an open problem in [Y. Wang, Distance two labelling of Halin graphs, Ars Combin. 114 (2014), 331-343].

引用

页码：217 / 231

页数：15

共 16 条

[1] LENGTHS OF CYCLES IN HALIN GRAPHS [J].

BONDY, JA ;

LOVASZ, L .

JOURNAL OF GRAPH THEORY, 1985, 9 (03) :397-410

[2] The 2-dipath chromatic number of Halin graphs [J].

Chen Min ;

Wang Weifan .

INFORMATION PROCESSING LETTERS, 2006, 99 (02) :47-53

[3] Acyclic List Edge Coloring of Graphs [J].

Lai, Hsin-Hao ;

Lih, Ko-Wei .

JOURNAL OF GRAPH THEORY, 2013, 72 (03) :247-266

[4] The strong chromatic index of Halin graphs [J].

Lai, Hsin-Hao ;

Lih, Ko-Wei ;

Tsai, Ping-Ying .

DISCRETE MATHEMATICS, 2012, 312 (09) :1536-1541

[5]

Lam PCB, 1997, NETWORKS, V30, P167, DOI 10.1002/(SICI)1097-0037(199710)30:3<167::AID-NET2>3.0.CO

[6]

2-J

[7] Coloring the square of a K4-minor free graph [J].

Lih, KW ;

Wang, WF ;

Zhu, XD .

DISCRETE MATHEMATICS, 2003, 269 (1-3) :303-309

[8] A bound on the chromatic number of the square of a planar graph [J].

Molloy, M ;

Salavatipour, MR .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) :189-213

[9] Minimum cycle bases of Halin graphs [J].

Stadler, PF .

JOURNAL OF GRAPH THEORY, 2003, 43 (02) :150-155

[10] Coloring the square of a planar graph [J].

van den Heuvel, J ;

McGuinness, S .

JOURNAL OF GRAPH THEORY, 2003, 42 (02) :110-124

← 1 2 →