Defective incidence coloring of graphs

被引：1

作者：

Bi, Huimin ^{[1
]}

Zhang, Xin ^{[1
]}

机构：

[1] Xidian Univ, Sch Math & Stat, Xian 710071, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2023年 / 443卷

基金：

中国国家自然科学基金;

关键词：

Incidence coloring; Defective coloring; Latin square; Outerplanar graph; Polynomial-time algorithm; STAR ARBORICITY;

D O I：

10.1016/j.amc.2022.127781

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We define the d-defective incidence chromatic number of a graph, generalizing the notion of incidence chromatic number, and determine it for some classes of graphs including trees, complete bipartite graphs, complete graphs, and outerplanar graphs. Fast algorithms for constructing the optimal d-defective incidence colorings of those graphs are presented. (c) 2022 Elsevier Inc. All rights reserved.

引用

页数：13

共 16 条

[1] THE STAR ARBORICITY OF GRAPHS [J].

ALGOR, I ;

ALON, N .

DISCRETE MATHEMATICS, 1989, 75 (1-3) :11-22

[2] The incidence game chromatic number [J].

Andres, Stephan Dominique .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (09) :1980-1987

[3]

[Anonymous], 1975, Utilitas Math

[4]

[Anonymous], 1975, Utilitas Math

[5]

Bender E. A., 2010, Lists, Decisions and Graphs with an Introduction to Probability

[6] Incidence choosability of graphs [J].

Benmedjdoub, Brahim ;

Bouchemakh, Isma ;

Sopena, Eric .

DISCRETE APPLIED MATHEMATICS, 2019, 265 :40-55

[7] Incidence coloring of Mycielskians with fast algorithm [J].

Bi, Huimin ;

Zhang, Xin .

THEORETICAL COMPUTER SCIENCE, 2021, 878 :1-10

[8] INCIDENCE AND STRONG EDGE COLORINGS OF GRAPHS [J].

BRUALDI, RA ;

MASSEY, JJQ .

DISCRETE MATHEMATICS, 1993, 122 (1-3) :51-58

[9]

CHARTRAND G, 1967, ANN I H POINCARE B, V3, P433

[10] ORIENTED INCIDENCE COLOURINGS OF DIGRAPHS [J].

Duffy, Christopher ;

MacGillivray, Gary ;

Ochem, Pascal ;

Raspaud, Andre .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) :191-210

← 1 2 →