Graph coloring in linear time
From MaRDI portal
Publication:921012
DOI10.1016/0095-8956(92)90042-VzbMath0709.05019MaRDI QIDQ921012
Publication date: 1992
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cycles in color-critical graphs ⋮ Linear-Time Approximation Algorithms for the Max Cut Problem ⋮ Problems on cycles and colorings ⋮ Congruence of cycle lengths and chromatic number ⋮ Circumference, chromatic number and online coloring ⋮ Uncolorable mixed hypergraphs ⋮ Orientations of graphs with prescribed weighted out-degrees ⋮ Coloring digraphs with forbidden cycles ⋮ A Strengthening on Odd Cycles in Graphs of Given Chromatic Number ⋮ Resource-sharing system scheduling and circular chromatic number ⋮ Ramsey numbers for tournaments ⋮ Chromatic number and orientations of graphs and signed graphs ⋮ 4-chromatic graphs with large odd girth ⋮ Circular colouring and orientation of graphs ⋮ Cycles and new bounds for the chromatic number