Rainbow Induced Subgraphs in Proper Vertex Colorings

• Autorzy: Kisielewicz A. , Szykuła M.
• Języki publikacji: EN

Abstrakty

EN

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

EN

rainbow; induced subgraph; vertex coloring; replication graph; C++

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 4
• Strony: 437--451
• Opis fizyczny: Bibliogr. 20 poz., tab., wykr.

Twórcy

autor

Kisielewicz A.

autor

Szykuła M.

• University of Wrocław, Department of Mathematics and Computer Science, pl. Grunwaldzki 2, 50-384 Wrocław, Poland,

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.