Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2-clique colorable. In this paper we prove that B1-EPG graphs (edge intersection graphs of paths on a grid, where each path has at most one bend) are 4-clique colorable. Moreover, given a B1-EPG representation of a graph, we provide a linear time algorithm that constructs a 4-clique coloring of it. © 2017 Elsevier B.V.

Registro:

Documento: Artículo
Título:Clique coloring B1-EPG graphs
Autor:Bonomo, F.; Mazzoleni, M.P.; Stein, M.
Filiación:Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación, Buenos Aires, Argentina
CONICET-Universidad de Buenos Aires. Instituto de Investigación en Ciencias de la Computación (ICC), Buenos Aires, Argentina
CONICET and Departamento de Matemática, FCE-UNLP, La Plata, Argentina
Departamento de Ingeniería Matemática, Universidad de Chile, Santiago, Chile
Palabras clave:Clique coloring; Edge intersection graphs; Paths on grids; Polynomial time algorithm
Año:2017
Volumen:340
Número:5
Página de inicio:1008
Página de fin:1011
DOI: http://dx.doi.org/10.1016/j.disc.2017.01.019
Título revista:Discrete Mathematics
Título revista abreviado:Discrete Math
ISSN:0012365X
CODEN:DSMHA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v340_n5_p1008_Bonomo

Referencias:

  • Bacsó, G., Gravier, S., Gyárfás, A., Preissmann, M., Sebö, A., Coloring the maximal cliques of graphs (2004) SIAM J. Discrete Math, 17 (3), pp. 361-376
  • Bondy, J.A., Murty, U.S.R., Graph Theory (2007), Springer New York; Campos, C.N., Dantas, S., de Mello, C.P., Colouring clique-hypergraphs of circulant graphs (2013) Graphs Combin, 29 (6), pp. 1713-1720
  • Cerioli, M.R., Korenchendler, A.L., Clique-Coloring circular-arc graphs (2009) Electron. Notes Discrete Math, 35, pp. 287-292
  • Cerioli, M.R., Petito, P., Clique-coloring UE and UEH graphs (2008) Electron. Notes Discrete Math, 30, pp. 201-206
  • Charbit, P., Penev, I., Thomassé, S., Trotignon, N., Perfect graphs of arbitrarily large clique-chromatic number (2016) J. Combin. Theory Ser. B, 116, pp. 456-464
  • Duffus, D., Kierstead, H.A., Trotter, W.T., Fibres and ordered set coloring (1991) J. Combin. Theory Ser. A, 58 (1), pp. 158-164
  • Duffus, D., Sands, B., Sauer, N., Woodrow, R.E., Two-colouring all two-element maximal antichains (1991) J. Combin. Theory Ser. A, 57 (1), pp. 109-116
  • Epstein, D., Golumbic, M.C., Morgenstern, G., Approximation algorithms for B1-EPG graphs (2013) Algorithms and Data Structures - 13th International Symposium, 8037, pp. 328-340. , Springer, WADS 2013, London, on, Canada, August 12-14, Proceedings, Lecture Notes in Computer Science
  • Golumbic, M.C., Lipshteyn, M., Stern, M., Edge intersection graphs of single bend paths on a grid (2009) Networks, 54 (3), pp. 130-138
  • Heldt, D., Knauer, K.B., Ueckerdt, T., Edge-intersection graphs of grid paths: The bend-number (2014) Discrete Appl. Math, 167, pp. 144-162
  • Kratochvíl, J., Tuza, Z., On the complexity of bicoloring clique hypergraphs of graphs (2002) J. Algorithms, 45 (1), pp. 40-54
  • Mycielski, J., Sur le coloriage des graphs (1955) Colloq. Math, 3, pp. 161-162
  • Poon, H., (2000) Coloring Clique Hypergraphs (Master's thesis), , West Virginia University
  • Rose, D.J., Tarjan, R.E., Lueker, G.S., Algorithmic aspects of vertex elimination on graphs (1976) SIAM J. Comput, 5 (2), pp. 266-283

Citas:

---------- APA ----------
Bonomo, F., Mazzoleni, M.P. & Stein, M. (2017) . Clique coloring B1-EPG graphs. Discrete Mathematics, 340(5), 1008-1011.
http://dx.doi.org/10.1016/j.disc.2017.01.019
---------- CHICAGO ----------
Bonomo, F., Mazzoleni, M.P., Stein, M. "Clique coloring B1-EPG graphs" . Discrete Mathematics 340, no. 5 (2017) : 1008-1011.
http://dx.doi.org/10.1016/j.disc.2017.01.019
---------- MLA ----------
Bonomo, F., Mazzoleni, M.P., Stein, M. "Clique coloring B1-EPG graphs" . Discrete Mathematics, vol. 340, no. 5, 2017, pp. 1008-1011.
http://dx.doi.org/10.1016/j.disc.2017.01.019
---------- VANCOUVER ----------
Bonomo, F., Mazzoleni, M.P., Stein, M. Clique coloring B1-EPG graphs. Discrete Math. 2017;340(5):1008-1011.
http://dx.doi.org/10.1016/j.disc.2017.01.019