On-Line Coloring and Recursive Graph Theory

DOI10.1137/S0895480192224737zbMATH Open0795.05058OpenAlexW2130271612MaRDI QIDQ4287941FDOQ4287941

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

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 $

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)

Cited In (34)

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

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)