O(VE) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth

DOI10.1016/J.DISC.2025.114502MaRDI QIDQ6973980zbMATH OpenFDO

Authors Manouchehr Zaker

Publication date 10 June 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114502

zbMATH Keywords

block graphsfirst-fit coloringgirthgraph coloringGrundy number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A lower bound for approximating the Grundy number
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Coloring inductive graphs on-line
• Complexity of Grundy coloring and its variants
• First-fit chromatic numbers of \(d\)-degenerate graphs
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• First-fit colorings of graphs with no cycles of a prescribed even length
• scientific article; zbMATH DE number 65699 (Why is no real title available?)
• scientific article; zbMATH DE number 3800939 (Why is no real title available?)
• Inequalities for the first-fit chromatic number
• Inequalities for the Grundy chromatic number of graphs
• Introduction to algorithms.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• More bounds for the Grundy number of graphs
• New bounds for the chromatic number of graphs
• On the Grundy and b-chromatic numbers of a graph
• On-line and first fit colorings of graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Results on the Grundy chromatic number of graphs
• Some perfect coloring properties of graphs
• Tight bounds for online coloring of basic graph classes
• Upper bounds for some graph invariants in terms of blocks and cut-vertices

Cited in

(1)

• On z-coloring and \(\mathrm{b}^\ast \)-coloring of graphs as improved variants of the b-coloring

This page was built for publication: \(\mathcal{O}(VE)\) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth

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