Graph coloring in linear time (Q921012): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 18:22, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph coloring in linear time |
scientific article |
Statements
Graph coloring in linear time (English)
0 references
1992
0 references
We provide fast algorithms for finding proper vertex colorings of a graph with a small number of colors, when a suitable orientation is given on the edges. Moreover, generalizing Minty's and Gallai and Roy's classic results on oriented paths and cycles vs. chromatic number, we prove new sufficient conditions insuring that a graph is k-colorable. The main idea in the proofs is to apply directed and weighted variants of depth-first- search.
0 references
polynomial algorithms
0 references
vertex colorings
0 references
orientation
0 references
depth-first-search
0 references