More about Subcolorings
作者： Hajo Broersma , Fedor V. Fomin , Jaroslav Nešetřil , Gerhard J. Woeginger
关键词:
摘要: A subcoloring is a vertex coloring of graph in which every color class induces disjoint union cliques. We derive number results on the combinatorics, algorithmics, and complexity subcolorings.On negative side, we prove that 2-subcoloring NP-hard for comparability graphs, 3-subcoloring AT-free graphs complements planar graphs. On positive polynomial time algorithms r-subcoloring interval permutation Moreover, asymptotically best possible upper bounds subchromatic chordal terms vertices.
springer.com
sci-hub.st 参考文章(14)
Klaus W. Wagner, Monotonic Coverings of Finite Sets. Journal of Automata, Languages and Combinatorics. ,vol. 20, pp. 633- 639 ,(1984)
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
Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad, Graph Classes: A Survey ,(1987)
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
Demetrios Achlioptas, The complexity of G-free colourability Discrete Mathematics. ,vol. 165-166, pp. 21- 30 ,(1997) , 10.1016/S0012-365X(97)84217-3
Paul Erdös, Some remarks on the theory of graphs Bulletin of the American Mathematical Society. ,vol. 53, pp. 292- 294 ,(1947) , 10.1090/S0002-9904-1947-08785-1
John Gimbel, Dieter Kratsch, Lorna Stewart, On cocolourings and cochromatic numbers of graphs Discrete Applied Mathematics. ,vol. 48, pp. 111- 127 ,(1994) , 10.1016/0166-218X(92)00121-2
Paul Erdös, John Gimbel, Dieter Kratsch, Some extremal results in cochromatic and dichromatic theory Journal of Graph Theory. ,vol. 15, pp. 579- 585 ,(1991) , 10.1002/JGT.3190150604
Uriel Feige, Joe Kilian, Zero Knowledge and the Chromatic Number Journal of Computer and System Sciences. ,vol. 57, pp. 187- 199 ,(1998) , 10.1006/JCSS.1998.1587