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