On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $

DOI10.1137/S0895480191218861zbMath0839.05039OpenAlexW1995855402MaRDI QIDQ4863971

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

Publication date: 5 June 1996

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

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

zbMATH Keywords

greedy algorithmgraph coloringon-line algorithmon-line graphalgorithm First-Fit

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

A coloring problem for weighted graphs ⋮ A randomized algorithm for online unit clustering ⋮ Coloring interval graphs with First-Fit ⋮ First-fit colorings of graphs with no cycles of a prescribed even length ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ On-line coloring of perfect graphs ⋮ Lower Bounds for On-line Graph Colorings ⋮ An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ Bounds for the Grundy chromatic number of graphs in terms of domination number ⋮ Coloring graphs with no induced five‐vertex path or gem ⋮ Inequalities for the Grundy chromatic number of graphs ⋮ More bounds for the Grundy number of graphs ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ On-line graph coloring of \({\mathbb{P}_5}\)-free graphs ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Reverse Mathematics and Grundy colorings of graphs ⋮ A Dichotomy Theorem for First-Fit Chain Partitions ⋮ Variable sized online interval coloring with bandwidth ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ An improved algorithm for online unit clustering ⋮ Bounded families for the on-line \(t\)-relaxed coloring ⋮ On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs

This page was built for publication: On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $