On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
From MaRDI portal
Publication:4699166
DOI10.1137/S089548019631030XzbMath0940.05029MaRDI QIDQ4699166
Jenő Lehel, Zoltán Király, András Gyárfás
Publication date: 23 November 1999
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Adding isolated vertices makes some greedy online algorithms optimal ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ On-line 3-chromatic graphs. II: Critical graphs ⋮ On-line graph coloring of \({\mathbb{P}_5}\)-free graphs ⋮ On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs