On-line 3-chromatic graphs. II: Critical graphs

DOI10.1016/S0012-365X(96)00359-7zbMath0885.05066WikidataQ127179063 ScholiaQ127179063MaRDI QIDQ1377872

Zoltán Király, András Gyárfás, Jenő Lehel

Publication date: 15 April 1998

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmcritical graphson-line chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (12)

A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs ⋮ Results on the Grundy chromatic number of graphs ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete ⋮ Computational aspects of greedy partitioning of graphs ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ On Computational Aspects of Greedy Partitioning of Graphs ⋮ Minimum order of graphs with given coloring parameters ⋮ Complexity of Grundy coloring and its variants ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ New potential functions for greedy independence and coloring

Cites Work

• An on-line graph coloring algorithm with sublinear performance ratio
• On the on-line chromatic number of the family of on-line 3-chromatic graphs
• On-line and first fit colorings of graphs
• On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On-line 3-chromatic graphs. II: Critical graphs