Graphs of girth at least 7 have high b-chromatic number

被引：14

作者：

Campos, V. ^{[1
]}

Lima, C. ^{[2
]}

Silva, A. ^{[3
]}

机构：

[1] Univ Fed Ceara, Dept Comp, Fortaleza, Ceara, Brazil

[2] Univ Fed Rio de Janeiro, COPPE, BR-21941 Rio De Janeiro, Brazil

[3] Univ Fed Ceara, Dept Matemat, Fortaleza, Ceara, Brazil

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2015年 / 48卷

关键词：

REGULAR GRAPHS;

D O I：

10.1016/j.ejc.2015.02.017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A b-coloring of a graph is a proper coloring of its vertices such that every color class contains a vertex that has neighbors in all other color classes. The b-chromatic number of a graph is the largest integer b(G) such that the graph has a b-coloring with b(G) colors. This metric is upper bounded by the largest integer m(G) for which G has at least m(G) vertices with degree at least m(G) - 1. There are a number of results reporting that graphs with high girth have high b-chromatic number when compared to m(G). Here, we prove that every graph with girth at least 7 has b-chromatic number at least m(G) - 1. Our proof also yields a polynomial algorithm that produces an optimal b-coloring of these graphs. (C) 2015 Elsevier Ltd. All rights reserved.

引用

页码：154 / 164

页数：11

共 13 条

[1] On b-colorings in regular graphs [J].