NP completeness of the edge precoloring extension problem on bipartite graphs

被引：27

作者：

Fiala, J

机构：

[1] Charles Univ, Inst Theoret Comp Sci, ITI, Prague 11800 1, Czech Republic

[2] Charles Univ, Dept Appl Math, KAM, CR-11800 Prague 1, Czech Republic

来源：

JOURNAL OF GRAPH THEORY | 2003年 / 43卷 / 02期

关键词：

graph coloring; precoloring extension; computational complexity;

D O I：

10.1002/jgt.10088

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the following problem is NP complete: Let G be a cubic bipartite graph and f be a precoloring of a subset of edges of G using at most three colors. Can f be extended to a proper edge 3-coloring of the entire graph G? This result provides a natural counterpart to classical Holyer's result on edge 3-colorability of cubic graphs and a strengthening of results on precoloring extension of perfect graphs. (C) 2003 Wiley Periodicals, Inc.

引用

页码：156 / 160

页数：5

共 7 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] PRECOLORING EXTENSION .1. INTERVAL-GRAPHS [J].

BIRO, M ;

HUJTER, M ;

TUZA, Z .

DISCRETE MATHEMATICS, 1992, 100 (1-3) :267-279

[3]

CARAGIANNIS I, 2001, LECT NOTES COMPUTER, V2204, P21

[4]

Fiala J., 2002, Discuss. Math. Graph Theory, V22, P89, DOI [10.7151/dmgt.1159, DOI 10.7151/DMGT.1159]

[5] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[6]

Kratochvil J, 1997, J GRAPH THEOR, V25, P207, DOI 10.1002/(SICI)1097-0118(199707)25:3<207::AID-JGT4>3.0.CO

[7]

2-P

← 1 →