Biclique edge-choosability in some classes of graphs

• Gabriel A. G. Sobral UFPR
• Marina Groshaus CONICET
• André L. P. Guedes UFPR

DOI: https://doi.org/10.5753/etc.2017.3203

Resumo

In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K₃-free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K₃-free and chordal bipartite graphs for any given 2-list assignment to edges.

Referências

Figueiredo, C. M. H., Filho, H. B. M., Machado, R. C. S., and Dantas, S. (2013). Bicliquecolouring verification complexity and biclique-colouring power graphs. Discrete Applied Mathematics, 192:65–76.

Guedes, A., Ries, B., Sasaki, D., Groshaus, M., Machado, R. C. S., and Dantas, S. (2017). On star and biclique edge-colorings. International Transactions in Operational Research, 24(1-2):339–346.

Kratsch, D. and Kloks, T. (1995). Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph. Information Processing Letters, 55:11–16.

Marx, D. (2011). Complexity of clique coloring and related problems. Theoretical Computer Science, 412:3487–3500.

Rubin, A. L., Taylor, H., and Erdös, P. (1979). Choosability in graphs. Congr. Numer, 26:125–157.

Soulignac, F. J., Groshaus, M., and Terlisky, P. (2012). The star and biclique coloring and choosability problems. Journal of Graph Algorithms and Applications, 18:347–383.

Terlisky, P. (2010). Biclique-coloreo de grafos. Master’s thesis, Universidad de Buenos Aires.