Coloring the cliques of line graphs

被引：5

作者：

Bacso, Gabor ^{[1
]}

Ryjacek, Zdenek ^{[2
]}

Tuza, Zsolt ^{[3
,4
]}

机构：

[1] Hungarian Acad Sci, Comp & Automat Inst, Kende U 13-17, H-1111 Budapest, Hungary

[2] Univ West Bohemia, Dept Math, Plzen 30614, Czech Republic

[3] Hungarian Acad Sci, Alfred Renyi Inst Math, Realtanoda U 13-15, H-1053 Budapest, Hungary

[4] Univ Pannonia, Dept Comp Sci & Syst Technol, Egyet U 10, H-8200 Veszprem, Hungary

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 11期

关键词：

Chromatic number; Weak coloring; Clique chromatic number; Clique chromatic index; Line graph; Ramsey theory; TRANSVERSAL SETS; PERFECT GRAPHS;

D O I：

10.1016/j.disc.2016.11.011

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph. Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals 2 is NP-complete. We deal with the CCHN of the graph itself as well. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：2641 / 2649

页数：9

共 13 条

[1] CLIQUE-TRANSVERSAL SETS OF LINE GRAPHS AND COMPLEMENTS OF LINE GRAPHS [J].

ANDREAE, T ;

SCHUGHART, M ;

TUZA, Z .

DISCRETE MATHEMATICS, 1991, 88 (01) :11-20

[2]

[Anonymous], 1973, C NUM

[3] Coloring the maximal cliques of graphs [J].

Bacsó, G ;

Gravier, S ;

Gyárfás, A ;

Preissmann, M ;

Sebo, A .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 17 (03) :361-376

[4]

Bacsó G, 2009, DISCRETE MATH THEOR, V11, P15

[5]

Berge C., 1984, TOPICS PERFECT GRAPH, V21, P57

[6] STAR-CUTSETS AND PERFECT GRAPHS [J].

CHVATAL, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (03) :189-199

[7]

Chvatal V., 1984, Ann. Discrete Math, P63

[8] Path parity and perfection [J].

Everett, H ;

deFigueiredo, CMH ;

LinharesSales, C ;

Maffray, F ;

Porto, O ;

Reed, BA .

DISCRETE MATHEMATICS, 1997, 165 :233-252

[9]

Fredricksen H., 2000, Electron. J. Comb, V7, p#R32, DOI [10.37236/1510, DOI 10.37236/1510]

[10]

Graham R., 1990, RAMSEY THEORY

← 1 2 →