Name
Abstract | ||
|---|---|---|
In the 1960s, Minty, Gallai, and Roy proved that k -colorability of graphs has equivalent conditions in terms of the existence of orientations containing no cycles resp. paths with some orientation patterns. We give a common generalization of those classic results, providing new (necessary and sufficient) conditions for a graph to be k -chromatic. We also prove that if an orientation with those properties is available, or cycles of given lengths are excluded, then a proper coloring with a small number of colors can be found by a fast—linear or polynomial—algorithm. The basic idea of the proofs is to introduce directed and weighted variants of depth-first-search trees. Several related problems are raised. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0095-8956(92)90042-V | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
linear time,graph coloring | Complete coloring,Edge coloring,Discrete mathematics,Combinatorics,Fractional coloring,List coloring,Cycle graph,Directed graph,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
55 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
11 | 1.24 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zsolt Tuza | 1 | 1889 | 262.52 |