Registro completo de metadatos
Campo DC | Valor | Lengua/Idioma |
---|---|---|
dc.creator | Bonomo, Flavia | - |
dc.creator | Mazzoleni, María Pía | - |
dc.creator | Stein, Maya | - |
dc.date | 2018-08-22T14:22:30Z | - |
dc.date | 2018-08-22T14:22:30Z | - |
dc.date | 2017-05 | - |
dc.date | 2018-08-21T19:10:20Z | - |
dc.date.accessioned | 2019-04-29T15:42:48Z | - |
dc.date.available | 2019-04-29T15:42:48Z | - |
dc.date.issued | 2017-05 | - |
dc.identifier | Bonomo, Flavia; Mazzoleni, María Pía; Stein, Maya; Clique coloring B1-EPG graphs; Elsevier Science; Discrete Mathematics; 340; 5; 5-2017; 1008-1011 | - |
dc.identifier | 0012-365X | - |
dc.identifier | http://hdl.handle.net/11336/56526 | - |
dc.identifier | CONICET Digital | - |
dc.identifier | CONICET | - |
dc.identifier.uri | http://rodna.bn.gov.ar:8080/jspui/handle/bnmm/300133 | - |
dc.description | 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. | - |
dc.description | Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | - |
dc.description | Fil: Mazzoleni, María Pía. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina | - |
dc.description | Fil: Stein, Maya. Universidad de Chile; Chile | - |
dc.format | application/pdf | - |
dc.format | application/pdf | - |
dc.format | application/pdf | - |
dc.language | eng | - |
dc.publisher | Elsevier Science | - |
dc.relation | info:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1016/j.disc.2017.01.019 | - |
dc.relation | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0012365X17300298 | - |
dc.rights | info:eu-repo/semantics/restrictedAccess | - |
dc.rights | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | - |
dc.source | reponame:CONICET Digital (CONICET) | - |
dc.source | instname:Consejo Nacional de Investigaciones Científicas y Técnicas | - |
dc.source | instacron:CONICET | - |
dc.subject | CLIQUE COLORING | - |
dc.subject | EDGE INTERSECTION GRAPHS | - |
dc.subject | PATHS ON GRIDS | - |
dc.subject | POLYNOMIAL TIME ALGORITHM | - |
dc.subject | Ciencias de la Computación | - |
dc.subject | Ciencias de la Computación e Información | - |
dc.subject | CIENCIAS NATURALES Y EXACTAS | - |
dc.subject | Matemática Pura | - |
dc.subject | Matemáticas | - |
dc.subject | CIENCIAS NATURALES Y EXACTAS | - |
dc.subject | Ciencias de la Computación | - |
dc.subject | Ciencias de la Computación e Información | - |
dc.subject | CIENCIAS NATURALES Y EXACTAS | - |
dc.title | Clique coloring B1-EPG graphs | - |
dc.type | info:eu-repo/semantics/article | - |
dc.type | info:eu-repo/semantics/publishedVersion | - |
dc.type | info:ar-repo/semantics/articulo | - |
Aparece en las colecciones: | CONICET |
Ficheros en este ítem:
No hay ficheros asociados a este ítem.