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)

Review text

The Grundy (or First-Fit) chromatic number of a graph \(G = (V , E)\), denoted by \(\Gamma(G)\), is the maximum number of colors used by a First-Fit (greedy) coloring of \(G\). The determining \(\Gamma(G)\) is NP-complete for various classes of graphs. Also, there exists a constant \(c > 0\) such that the Grundy number is hard to approximate within the ratio \(c\). In this paper, the author obtains an \(\mathcal{O}(V E)\) algorithm to determine the Grundy number of block graphs, i.e. graphs in which every biconnected component is a complete graph and proves that the Grundy number of a general graph \(G\) with cut-vertices is upper bounded by the Grundy number of a block graph corresponding to \(G\). This provides a reasonable upper bound for the Grundy number of graphs with cut-vertices. It is proposed an \(\mathcal{O}(V E)\) algorithm to determine \(\Gamma(G)\) for graphs \(G\) whose girth \(g\) is at least \(2\Delta_{2}(G) + 1\), where \(\Delta_{2}(G) = \max_{u\in V} \max_{v\in N(u):d(v)\leq d(u)}d(v)\). This algorithm provides a polynomial time approximation algorithm within ratio \(\min\{1, (g +1)/(2\Delta_{2}(G)+2)\}\) for \(\Gamma(G)\) of general graphs \(G\) with girth \(g\).

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)