The b-chromatic index of direct product of graphs

被引：8

作者：

Koch, Ivo ^{[1
]}

Peterin, Iztok ^{[2
]}

机构：

[1] Univ Buenos Aires, Dept Comp Sci, Fac Exact & Nat Sci, Buenos Aires, DF, Argentina

[2] Univ Maribor, Fac Elect Engn & Comp Sci, Maribor 2000, Slovenia

来源：

DISCRETE APPLIED MATHEMATICS | 2015年 / 190卷

关键词：

b-chromatic index; Direct product; Regular graphs; NUMBER; BOUNDS;

D O I：

10.1016/j.dam.2015.04.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The b-chromatic index phi'(G) of a graph G is the largest integer k such that G admits a proper k-edge coloring in which every color class contains at least one edge incident to edges in every other color class. We give in this work bounds for the b-chromatic index of the direct product of graphs and provide general results for many direct products of regular graphs. In addition, we introduce an integer linear programming model for the b-edge coloring problem, which we use for computing exact results for the direct product of some special graph classes. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：109 / 117

页数：9

共 31 条

[1]

[Anonymous], 1988, Integer and combinatorial optimization

[2] Bounds for the b-chromatic number of G - v [J].

Balakrishnan, R. ;

Raj, S. Francis .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (09) :1173-1179

[3]

Balakrishnan R., 2008, P INT C ICDM, P53

[4] On the b-continuity property of graphs [J].

Barth, Dominique ;

Cohen, Johanne ;

Faik, Taoufik .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (13) :1761-1768

[5] On the b-coloring of P4-tidy graphs [J].

Betancur Velasquez, Clara Ines ;

Bonomo, Flavia ;

Koch, Ivo .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (01) :60-68

[6] On the b-Coloring of Cographs and P4-Sparse Graphs [J].

Bonomo, Flavia ;

Duran, Guillermo ;

Maffray, Frederic ;

Marenco, Javier ;

Valencia-Pabon, Mario .

GRAPHS AND COMBINATORICS, 2009, 25 (02) :153-167

[7] On the b-chromatic number of regular graphs [J].

Cabello, Sergio ;

Jakovac, Marko .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (13) :1303-1310

[8]

Campos V, 2009, ELECT NOTES DISCRET, V35, P281

[9]

Campos V, 2012, J BRAZ COMPUT SOC, V18, P375

[10]

Chaouche F., 2007, FAR E J APPL MATH, V26, P375

← 1 2 3 4 →