On-line and first fit colorings of graphs
From MaRDI portal
Publication:3804717
DOI10.1002/jgt.3190120212zbMath0657.05026OpenAlexW2166858292MaRDI QIDQ3804717
No author found.
Publication date: 1988
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.3190120212
colouring algorithmproper colouringon-line colouringfirst fit colouringfirst fit algorithmslargest clique size
Related Items
Lower bounds for on-line graph coloring, On the Nash number and the diminishing Grundy number of a graph, On the performance of the first-fit coloring algorithm on permutation graphs, New models of graph-bin packing, A randomized algorithm for online unit clustering, On-line dimension of semi-orders, Online Graph Coloring Against a Randomized Adversary, A tight bound for online colouring of disk graphs, Coloring interval graphs with First-Fit, First-fit colorings of graphs with no cycles of a prescribed even length, Radius two trees specify χ‐bounded classes, Results on the Grundy chromatic number of graphs, Online algorithms for the maximum \(k\)-colorable subgraph problem, Online promise problems with online width metrics, On Grundy and b-chromatic number of some families of graphs: a comparative study, On the on-line chromatic number of the family of on-line 3-chromatic graphs, On-line coloring of perfect graphs, Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable, On-line 3-chromatic graphs. II: Critical graphs, An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs, Radius two trees specify χ‐bounded classes, Bin packing with ``largest in bottom constraint: tighter bounds and generalizations, Obtaining online ecological colourings by generalizing first-fit, On the complexity of injective colorings and its generalizations, Grundy Distinguishes Treewidth from Pathwidth, THE GRAPH-BIN PACKING PROBLEM, Recoloring graphs via tree decompositions, Bounds for the Grundy chromatic number of graphs in terms of domination number, More results on the \(z\)-chromatic number of graphs, A new vertex coloring heuristic and corresponding chromatic number, Unnamed Item, On the online track assignment problem, A comparison of the Grundy and b-chromatic number of \(K_{2,t}\)-free graphs, Grundy number of corona product of some graphs, Online coloring of short intervals, Graph coloring with rejection, Limitations of current wireless link scheduling algorithms, Batch Coloring of Graphs, The connected greedy coloring game, Online coloring of hypergraphs, Tight bounds for online coloring of basic graph classes, A polynomial time approximation algorithm for dynamic storage allocation, Effective on-line coloring of \(P_ 5\)-free graphs, Online coloring of bipartite graphs with and without advice, Inequalities for the Grundy chromatic number of graphs, First-fit coloring on interval graphs has performance ratio at least 5, Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs, Online unit clustering: Variations on a theme, Complexity of Grundy coloring and its variants, The online graph bandwidth problem, An on-line competitive algorithm for coloring bipartite graphs without long induced paths, Batch coloring of graphs, On the max coloring problem, Recognition of split-graphic sequences, On the Grundy number of graphs with few \(P_4\)'s, On-line graph coloring of \({\mathbb{P}_5}\)-free graphs, Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors, The greedy algorithm is optimal for on-line edge coloring, First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs, Grundy number and products of graphs, On distance constrained labeling of disk graphs, Online coloring graphs with high girth and high odd girth, Online hypergraph coloring, A note on the online first-fit algorithm for coloring \(k\)-inductive graphs, On-line vertex-covering, Online Conflict-Free Colouring for Hypergraphs, On the Max Coloring Problem, On the Online Unit Clustering Problem, On-line approach to off-line coloring problems on graphs with geometric representations, R.e. Prime powers and total rigidity, Online coloring and a new type of adversary for online graph problems, A Dichotomy Theorem for First-Fit Chain Partitions, Open Problems on Graph Coloring for Special Graph Classes, On-line chain partitions of orders: a survey, Grundy number on -classes, Restricted coloring problems on graphs with few, An improved algorithm for online unit clustering, Tight Bounds for Online Coloring of Basic Graph Classes, Bounded families for the on-line \(t\)-relaxed coloring, On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs, The on-line first-fit algorithm for radio frequency assignment problems., Online independent sets., Online coloring and a new type of adversary for online graph problems, Advice complexity of maximum independent set in sparse and bipartite graphs, Coloring inductive graphs on-line, Two graph-colouring games, On-line coloring of geometric intersection graphs, On the mean chromatic number
