Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2017.01.019 | Discrete Mathematics |
Keywords | Field | DocType |
Clique coloring,Edge intersection graphs,Paths on grids,Polynomial time algorithm | Discrete mathematics,Edge coloring,Complete coloring,Indifference graph,Combinatorics,Fractional coloring,Chordal graph,Greedy coloring,Mathematics,Split graph,Graph coloring | Journal |
Volume | Issue | ISSN |
340 | 5 | 0012-365X |
Citations | PageRank | References |
3 | 0.40 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Flavia Bonomo | 1 | 226 | 28.95 |
| M. P. Mazzoleni | 2 | 12 | 4.05 |
| maya stein | 3 | 81 | 15.65 |