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
关键词
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