On-Line Coloring and Recursive Graph Theory

DOI10.1137/S0895480192224737zbMath0795.05058OpenAlexW2130271612MaRDI QIDQ4287941

S. G. Penrice, Henry A. Kierstead, William T. jun. Trotter

Publication date: 19 April 1994

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

Full work available at URL: https://doi.org/10.1137/s0895480192224737

zbMATH Keywords

graph coloringclique numberrecursive functionon-line vertex coloring algorithmradius-2 treerecursive cocomparability graph

Mathematics Subject Classification ID

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

Related Items (23)

On-line algorithms for ordered sets and comparability graphs ⋮ Coloring interval graphs with First-Fit ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ On-line coloring of perfect graphs ⋮ Classes of graphs that exclude a tree and a clique and are not vertex Ramsey ⋮ Lower Bounds for On-line Graph Colorings ⋮ An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ Feasible Graphs and Colorings ⋮ Graphs are not universal for online computability ⋮ Primitive recursive reverse mathematics ⋮ A structure of punctual dimension two ⋮ On the online track assignment problem ⋮ Online presentations of finitely generated structures ⋮ An easy subexponential bound for online chain partitioning ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ First-fit coloring of bounded tolerance graphs ⋮ Non-density in punctual computability ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ On-line chain partitions of orders: a survey ⋮ Antisymmetric flows and strong colourings of oriented graphs ⋮ Induced cycles and chromatic number ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY

This page was built for publication: On-Line Coloring and Recursive Graph Theory