Effective coloration
From MaRDI portal
Publication:4097267
DOI10.2307/2272247zbMath0331.02025OpenAlexW4231402170MaRDI QIDQ4097267
Publication date: 1976
Published in: The Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2272247
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Applications of computability and recursion theory (03D80)
Related Items (38)
Lower bounds for on-line graph coloring ⋮ A coloring problem for weighted graphs ⋮ On-line algorithms for ordered sets and comparability graphs ⋮ Recursive coloration of countable graphs ⋮ On-line coloring of perfect graphs ⋮ 1994 Annual Meeting of the Association for Symbolic Logic ⋮ An on-line graph coloring algorithm with sublinear performance ratio ⋮ Bin packing with ``largest in bottom constraint: tighter bounds and generalizations ⋮ Unbounded search and recursive graph problems ⋮ Finding domatic partitions in infinite graphs ⋮ Binary search and recursive graph problems ⋮ Prime labelings of infinite graphs ⋮ \(A\)-computable graphs ⋮ Online coloring of short intervals ⋮ Domatic partitions of computable graphs ⋮ On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case ⋮ Tight bounds for online coloring of basic graph classes ⋮ Online coloring of bipartite graphs with and without advice ⋮ The Mapmaker's dilemma ⋮ Computing planarity in computable planar graphs ⋮ Hamiltonian paths in infinite graphs ⋮ The online graph bandwidth problem ⋮ On-line graph coloring of \({\mathbb{P}_5}\)-free graphs ⋮ Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors ⋮ A theory of recursive dimension of ordered sets ⋮ Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes ⋮ R.e. Prime powers and total rigidity ⋮ Online chromatic number is PSPACE-complete ⋮ Max-coloring of vertex-weighted graphs ⋮ Online coloring and a new type of adversary for online graph problems ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Tight Bounds for Online Coloring of Basic Graph Classes ⋮ Recursive Euler and Hamilton Paths ⋮ On the finiteness of the recursive chromatic number ⋮ Index sets for \(\Pi^0_1\) classes ⋮ Unnamed Item ⋮ Online independent sets. ⋮ Online coloring and a new type of adversary for online graph problems
This page was built for publication: Effective coloration
