On-Line 3-Chromatic Graphs I. Triangle-Free Graphs

DOI10.1137/S089548019631030XzbMATH Open0940.05029MaRDI QIDQ4699166FDOQ4699166

Jeno 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)

Recommendations

• On-line 3-chromatic graphs. II: Critical graphs
• On the on-line chromatic number of the family of on-line 3-chromatic graphs
• On-Line Coloring and Recursive Graph Theory

zbMATH Keywords

characterizationforbidden subgraphson-line coloringone-line 3-coloring algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Cited In (5)

• On-line graph coloring of \({\mathbb{P}_5}\)-free graphs
• On the on-line chromatic number of the family of on-line 3-chromatic graphs
• Adding isolated vertices makes some greedy online algorithms optimal
• On-line 3-chromatic graphs. II: Critical graphs
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs

This page was built for publication: On-Line 3-Chromatic Graphs I. Triangle-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699166)