Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous
作者： Hajo Broersma , Fedor V. Fomin , Jan Kratochvíl , Gerhard J. Woeginger
关键词:
摘要: We consider the problem of coloring a planar graph with minimum number colors such that each color class avoids one or more forbidden graphs as subgraphs. perform detailed study computational complexity this problem.We present complete picture for case single connected (induced non-induced) subgraph. The 2-coloring is NP-hard if subgraph tree at least two edges, and it polynomially solvable in all other cases. 3-coloring path, also derive results several sets cycles.
springer.com
core.ac.uk
utwente.nl
sci-hub.st 参考文章(19)
Chính T. Hoàng, Van Bang Le, P_4-Colorings and P_4-Bipartite Graphs Discrete Mathematics & Theoretical Computer Science. ,vol. 4, pp. 109- 122 ,(2001)
Jiří Fiala, Klaus Jansen, Van Bang Le, Eike Seidel, Graph Subcolorings: Complexity and Algorithms workshop on graph theoretic concepts in computer science. pp. 154- 165 ,(2001) , 10.1007/3-540-45477-2_15
L Lesniak, G Chartrand, D R Lick, Y Alavi, C E Wall, Graph theory with applications to algorithms and computer science John Wiley & Sons, Inc.. ,(1985)
M.O. Albertson, R.E. Jamison, S.T. Hedetniemi, S.C. Locke, The subchromatic number of a graph Discrete Mathematics. ,vol. 74, pp. 33- 49 ,(1989) , 10.1016/0012-365X(89)90196-9
Gary Chartrand, Hudson V. Kronk, Curtiss E. Wall, The point-arboricity of a graph Israel Journal of Mathematics. ,vol. 6, pp. 169- 175 ,(1968) , 10.1007/BF02760181
Marietjie Frick, Michael A. Henning, Extremal results on defective colorings of graphs Discrete Mathematics. ,vol. 126, pp. 151- 158 ,(1994) , 10.1016/0012-365X(94)90260-7
Wayne Goddard, Acyclic colorings of planar graphs Discrete Mathematics. ,vol. 91, pp. 91- 94 ,(1991) , 10.1016/0012-365X(91)90166-Y
K. S. Poh, On the linear vertex-arboricity of a planar graph Journal of Graph Theory. ,vol. 14, pp. 73- 75 ,(1990) , 10.1002/JGT.3190140108
J. I. Brown, D. G. Corneil, ON UNIQUELY -G k-COLOURABLE GRAPHS Quaestiones Mathematicae. ,vol. 15, pp. 477- 487 ,(1992) , 10.1080/16073606.1992.9631706
Hoàng-Oanh Le, Van Bang Le, The NP-completeness of (1,r)-subcolorability of cubic graphs Information Processing Letters. ,vol. 81, pp. 157- 162 ,(2002) , 10.1016/S0020-0190(01)00205-8