期刊
EUROPEAN JOURNAL OF COMBINATORICS
卷 33, 期 4, 页码 592-609出版社
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.ejc.2011.12.002
关键词
-
类别
资金
- Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq)
- CAPES (Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior, Brasil)
- FAPEMIG (Fundacao de Amparo a Pesquisa do Estado de Minas Gerais)
- Universita di Roma Tor Vergata
Given a graph G with maximum degree Delta >= 3, we prove that the acyclic edge chromatic number a' (G) of G is such that a'(G) <= [9.62(Delta - 1)]. Moreover we prove that: a' (G) <= [6.42(Delta - 1)] if G has girth g >= 5; a' (G) <= [5.7(Delta - 1)] if G has girth g >= 7; a' (G) <= [4.52(Delta - 1)] if g >= 53; a' (G) <= Delta + 2 if g >= [25.84 Delta log Delta(1 + 4.1/log Delta]. We further prove that the acyclic (vertex) chromatic number a(G) of G is such that a(G) <= [6.59 Delta(4/3) + 3.3 Delta]. We also prove that the star-chromatic number chi(s)(G) of G is such that chi(s)(G) <= [4.34 Delta(3/2) + 1.5 Delta]. We finally prove that the beta-frugal chromatic number chi(beta)(G) of G is such that chi(beta)(G) <= [max{k(1)(similar to beta)Delta, k(2)(beta)Delta(1+1 beta)/(beta!)(1/beta)}]. where k(1)(beta) and k(2)(beta) are decreasing functions of beta such that k(1)(beta) is an element of [4,6] and k(2)(beta) is an element of [2, 5]. To obtain these results we use an improved version of the Lovasz Local Lemma due to Bissacot et al. (2011) [6]. (C) 2011 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据