Clique coloring B1-EPG graphs
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 gr...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2017
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 04887caa a22005657a 4500 | ||
|---|---|---|---|
| 001 | PAPER-15024 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204539.0 | ||
| 008 | 190410s2017 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85011982238 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a DSMHA | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a Clique coloring B1-EPG graphs |
| 260 | |b Elsevier B.V. |c 2017 | ||
| 270 | 1 | 0 | |m Bonomo, F.; Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de ComputaciónArgentina; email: fbonomo@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Cerioli, M.R., Korenchendler, A.L., Clique-Coloring circular-arc graphs (2009) Electron. Notes Discrete Math, 35, pp. 287-292 | ||
| 504 | |a Cerioli, M.R., Petito, P., Clique-coloring UE and UEH graphs (2008) Electron. Notes Discrete Math, 30, pp. 201-206 | ||
| 504 | |a 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 | ||
| 504 | |a Duffus, D., Kierstead, H.A., Trotter, W.T., Fibres and ordered set coloring (1991) J. Combin. Theory Ser. A, 58 (1), pp. 158-164 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Golumbic, M.C., Lipshteyn, M., Stern, M., Edge intersection graphs of single bend paths on a grid (2009) Networks, 54 (3), pp. 130-138 | ||
| 504 | |a Heldt, D., Knauer, K.B., Ueckerdt, T., Edge-intersection graphs of grid paths: The bend-number (2014) Discrete Appl. Math, 167, pp. 144-162 | ||
| 504 | |a Kratochvíl, J., Tuza, Z., On the complexity of bicoloring clique hypergraphs of graphs (2002) J. Algorithms, 45 (1), pp. 40-54 | ||
| 504 | |a Mycielski, J., Sur le coloriage des graphs (1955) Colloq. Math, 3, pp. 161-162 | ||
| 504 | |a Poon, H., (2000) Coloring Clique Hypergraphs (Master's thesis), , West Virginia University | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación, Buenos Aires, Argentina | ||
| 593 | |a CONICET-Universidad de Buenos Aires. Instituto de Investigación en Ciencias de la Computación (ICC), Buenos Aires, Argentina | ||
| 593 | |a CONICET and Departamento de Matemática, FCE-UNLP, La Plata, Argentina | ||
| 593 | |a Departamento de Ingeniería Matemática, Universidad de Chile, Santiago, Chile | ||
| 690 | 1 | 0 | |a CLIQUE COLORING |
| 690 | 1 | 0 | |a EDGE INTERSECTION GRAPHS |
| 690 | 1 | 0 | |a PATHS ON GRIDS |
| 690 | 1 | 0 | |a POLYNOMIAL TIME ALGORITHM |
| 700 | 1 | |a Mazzoleni, M.P. | |
| 700 | 1 | |a Stein, M. | |
| 773 | 0 | |d Elsevier B.V., 2017 |g v. 340 |h pp. 1008-1011 |k n. 5 |p Discrete Math |x 0012365X |w (AR-BaUEN)CENRE-309 |t Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85011982238&doi=10.1016%2fj.disc.2017.01.019&partnerID=40&md5=4595b79fd83f9fd773b983f9766b0a37 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.disc.2017.01.019 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_0012365X_v340_n5_p1008_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v340_n5_p1008_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_0012365X_v340_n5_p1008_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 75977 | ||