Two bounds of chromatic number in graphs coloring problem

被引：0

作者：

Gueham, Assia ^{[1
,2
]}

Nagih, Anass ^{[3
]}

Haddadene, Hacene Ait ^{[2
]}

机构：

[1] Univ Algiers, Algiers, Algeria

[2] USTHB Univ, LaROMaD Lab, Algiers 16111, Algeria

[3] Lorraine Univ, LCOMS Lab, F-57045 Metz 01, France

来源：

2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT) | 2014年

关键词：

Chromatic number; Graph Orientation; Graph Coloring;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we focus on the coloration approach and estimation of chromatic number. We propose an upper bound of a chromatic number based on the orientation algorithm described in [4]. This upper bound is improved by developing a novel coloration algorithm. Finally, we make a theoretical and empirical comparison of our bounds with Brooks's bound and Reed's conjecture [15] for class of triangle-free graphs.

引用

页码：292 / 296

页数：5

共 17 条

[1] Bounding χ in terms of ω and Δ for some classes of graphs [J].

Aravind, N. R. ;

Karthick, T. ;

Subramanian, C. R. .

DISCRETE MATHEMATICS, 2011, 311 (12) :911-920

[2]

Berry L.A., 2013, DISCRETE MATH, V313

[3]

Brooks R. L, 1941, P CAMBRIDGE PHILOS S

[4]

Gueham A., 2012, APPL MATH SCI, V6, P5439

[5]

Ito T., 2009, ELECT NOTES DISCRETE, V35

[6]

Jensen T., 1995, Graph Coloring Problems, P115

[7] THE CHROMATIC NUMBER OF GRAPHS WHICH INDUCE NEITHER K1,3 NOR K5-E [J].

KIERSTEAD, HA ;

SCHMERL, JH .

DISCRETE MATHEMATICS, 1986, 58 (03) :253-262

[8]

King A.D., 2007, EUROPEAN J COMBINATO, V28

[9] Bounding χ in Terms of ω and Δ for Quasi-Line Graphs [J].

King, Andrew D. ;

Reed, Bruce A. .

JOURNAL OF GRAPH THEORY, 2008, 59 (03) :215-228

[10] Some results on Reed's Conjecture about ω, Δ, and χ with respect to α [J].

Kohl, Anja ;

Schiermeyer, Ingo .

DISCRETE MATHEMATICS, 2010, 310 (09) :1429-1438

← 1 2 →