On-Line Coloring and Recursive Graph Theory

DOI10.1137/S0895480192224737MaRDI QIDQ4287941zbMATHOpenAlexFDO

Authors S. G. Penrice, H. A. Kierstead, William T. 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

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

Recommendations

• scientific article; zbMATH DE number 65699
• On-line and first fit colorings of graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $

Cited in

(33)

• On-line coloring of perfect graphs
• Bounded families for the on-line \(t\)-relaxed coloring
• On the online track assignment problem
• Antisymmetric flows and strong colourings of oriented graphs
• Online, computable and punctual structure theory
• Lower bounds for on-line graph colorings
• An on-line competitive algorithm for coloring \(P_8\)-free bipartite graphs
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Non-density in punctual computability
• Online edge coloring via tree recurrences and correlation decay
• PUNCTUAL CATEGORICITY AND UNIVERSALITY
• Online hypergraph coloring with rejection
• A structure of punctual dimension two
• On-line algorithms for ordered sets and comparability graphs
• On-line approach to off-line coloring problems on graphs with geometric representations
• scientific article; zbMATH DE number 1303205 (Why is no real title available?)
• On the on-line chromatic number of the family of on-line 3-chromatic graphs
• Graphs are not universal for online computability
• On-line chain partitions of orders: a survey
• Open problems on graph coloring for special graph classes
• Induced cycles and chromatic number
• An on-line competitive algorithm for coloring bipartite graphs without long induced paths
• First-fit coloring of bounded tolerance graphs
• Online presentations of finitely generated structures
• scientific article; zbMATH DE number 65708 (Why is no real title available?)
• An easy subexponential bound for online chain partitioning
• Classes of graphs that exclude a tree and a clique and are not vertex Ramsey
• Coloring interval graphs with First-Fit
• On-line and first fit colorings of graphs
• Primitive recursive reverse mathematics
• Online Dual Edge Coloring of Paths and Trees
• Randomized online graph coloring
• Feasible Graphs and Colorings

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

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