Name
Abstract | ||
|---|---|---|
We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jctb.2021.07.002 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Coloring,Surfaces,Triangle-free | Complete coloring,Discrete mathematics,Edge coloring,Combinatorics,Fractional coloring,Algorithm,Hopcroft–Karp algorithm,Independent set,Suurballe's algorithm,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | ISSN | Citations |
152 | 0095-8956 | 2 |
PageRank | References | Authors |
0.41 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zdenek Dvorak | 1 | 104 | 16.60 |
| Daniel Král' | 2 | 129 | 18.89 |
| Robin Thomas | 3 | 457 | 35.92 |