Czasopismo
2011
|
Vol. 111, nr 4
|
437-451
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
Given a graph H we define p(H) to be the minimum order of a graph G such that every proper vertex coloring of G contains a rainbow induced subgraph isomorphic to H. We give upper and lower bounds for p(H), compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of (H) for paths. A part of this research has been guided by a computer search and, accordingly, some computational results are presented. A special motivation comes from research in on-line coloring.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
437-451
Opis fizyczny
Bibliogr. 20 poz., tab., wykr.
Twórcy
autor
autor
- University of Wrocław, Department of Mathematics and Computer Science, pl. Grunwaldzki 2, 50-384 Wrocław, Poland, marek.szykula@ii.uni.wroc.pl
Bibliografia
- [1] M. Axenovich, J. Choi, On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph, Electron. J. Combinatorics, 17(1) (2010), 12 pp.
- [2] M. Axenovich, P. Iverson, Edge-colorings avoiding rainbow and monochromatic subgraphs, Discrete Math., 308 (20), (2008), 4710-4723.
- [3] M. Axenovich, R. Martin, Avoiding rainbow induced subgraphs in vertex-colorings. Electron. J. Combinatorics 15(1), (2008), 23 pp.
- [4] M. Axenovich, C. Sackett, Avoiding rainbow induced subgraphs in edge-colorings, Australaisian J. Combinatorics, 44, (2009), 287-296.
- [5] H. Broersma, A. Capponi, G. Paulusma, A new algorithm for on-line coloring bipartite graphs. SIAM J. Discrete Math. 22(1), (2008), 72-91.
- [6] A. Cherubini, A. Kisielewicz, B. Piochi, On the length of shortest 2-collapsing words, Discrete Mathematics and Theoretical Computer Science 11 (2009), 33-44.
- [7] R. Diestel, "Graph Theory", Springer-Verlag Heidelberg, New York 2005.
- [8] G. J. Chaitin, Register allocation and spilling via graph colouring, in: Proc. 1982 SIGPLAN Symposium on Compiler Construction, pp. 98-105.
- [9] G. Chartrand, P. Zhang, "Chromatic Graph Theory", Discrete Mathematics and Its Applications, Boca Raton 2009.
- [10] P. Gawrychowski, A. Kisielewicz, M. Gutan, On the problem of freenes of multiplicative matrix semigroups, Theoretical Computer Science 411 (2010), 1115-1120.
- [11] D. S. Johnson, M. Trick (eds.) "Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993", vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Providence 1996.
- [12] D. Marx, Graph colouring problems and their applications in scheduling, Periodica Polytechnica, Electrical Engineering, 48 (2004), 11-16.
- [13] B. McKay, Combinatorial data: graphs page, http://cs.anu.edu.au/∼bdm/.
- [14] G. Matecki G., On-line graph coloring on a bounded board, PhD Thesis, Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University (2006). http://tcs.uj.edu.pl/docs.php?id=8
- [15] P. Keevash, D. Mubayi, B. Sudakov, J. Verstra¨ete, Rainbow Turán Problems, Combinatorics, Probability, and Computing, 16 (1) (2007). pp. 109-126.
- [16] H. A. Kierstead, S. G. Penrice,W. T. Trotter, On-line and first-fit coloring of graphs which do not induce P5, SIAM Journal of Discrete Mathematics 8 (1995), 485-498.
- [17] H. A. Kierstead, W. T. Trotter, Colorful induced subgraphs, Discrete Math. 101 (1992), no. 1-3, 165-169.
- [18] Y. Kohayakawa, T. Łuczak Sparse Anti-Ramsey Graphs, J. Combinatorial Theory, Series B 63(1995), 146-152.
- [19] J. O'Rourke, Galleries Need Fewer Mobile Guards: A Variation on Chvatal's Theorem, Geometriae Dedicata 14 (1983), 273-283.
- [20] F.S. Roberts, From garbage to rainbows: Generalizations of graph coloring and their applications, in: Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk (eds.), Graph Theory, Combinatorics, and Applications, vol. 2, Wiley, New York, 1991, pp. 1031-1052.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0021-0016