STAR COLORING OUTERPLANAR BIPARTITE GRAPHS

被引：1

作者：

Ramamurthi, Radhika ^{[1
]}

Sanders, Gina ^{[1
]}

机构：

[1] Calif State Univ, Dept Math, San Marcos, CA 92096 USA

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2019年 / 39卷 / 04期

关键词：

chromatic number; star coloring; outerplanar bipartite graph; ACYCLIC COLORINGS;

D O I：

10.7151/dmgt.2109

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known example that requires five colors.

引用

页码：899 / 908

页数：10

共 10 条

[1]

Albertson MO, 2004, ELECTRON J COMB, V11

[2] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

BORODIN, OV .

DISCRETE MATHEMATICS, 1979, 25 (03) :211-236

[3] 6-Star-Coloring of Subcubic Graphs [J].

Chen, Min ;

Raspaud, Andre ;

Wang, Weifan .

JOURNAL OF GRAPH THEORY, 2013, 72 (02) :128-145

[4] Star coloring of graphs [J].

Fertin, G ;

Raspaud, A ;

Reed, B .

JOURNAL OF GRAPH THEORY, 2004, 47 (03) :163-182

[5] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

GRUNBAUM, B .

ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) :390-408

[6] Star Coloring Bipartite Planar Graphs [J].

Kierstead, H. A. ;

Kuendgen, Andre ;

Timmons, Craig .

JOURNAL OF GRAPH THEORY, 2009, 60 (01) :1-10

[7]

Nesetril J, 2003, ALGORITHM COMBINAT, V25, P651

[8]

Sanders G., 2005, THESIS

[9]

Timmons C., 2007, THESIS

[10]

West D. B., 2001, INTRO GRAPH THEORY

← 1 →