Bounds for the Grundy chromatic number of graphs in terms of domination number

DOI10.36045/J.BBMS.211019MaRDI QIDQ6073792zbMATH OpenFDO

Authors Abbas Khaleghi, Manouchehr Zaker

Publication date 18 September 2023

Published in Bulletin of the Belgian Mathematical Society - Simon Stevin (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.04154

zbMATH Keywords

domination numberfirst-fit coloringgirthgraph coloringGrundy numberstar partitions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: For any graph $G$, the Grundy (or First-Fit) chromatic number of $G$, denoted by $Gamma(G)$ (also $ch{i}_{{}_{sfFF}}(G)$), is defined as the maximum number of colors used by the First-Fit (greedy) coloring of the vertices of $G$. Determining the Grundy number is $NP$-complete, and obtaining bounds for $Gamma(G)$ in terms of the known graph parameters is an active research topic. By a star partition of $G$ we mean any partition of $V(G)$ into say $V_1,ldots,V_k$ such that each $G[V_i]$ contains a vertex adjacent to any other vertex in $V_i$. In this paper using the star partition of graphs we obtain the first upper bounds for the Grundy number in terms of the domination number. We also prove some bounds in terms of the domination number and girth of graphs.

Review text

For a graph \(G=(V,E)\), a Grundy \(k\)-coloring of a graph \(G\) is a proper coloring of \(V(G)\) with colors \(\{1, 2, \dots, k\}\) such that for each color \(j\), any vertex colored \(j\) is adjacent to a vertex colored \(i\) for every \(i<j\). The Grundy chromatic number of \(G\) is the largest integer \(k\) such that there exists a Grundy \(k\)-coloring for \(G\). For a given ordering of \(V(G)\), the greedy coloring algorithm assigns the smallest available color to every vertex with respect to the ordering. It is known that the Grundy chromatic number of \(G\) equals the largest number of colors used by the greedy coloring algorithm of any ordering of \(V(G)\). A star partition of \(G\) is a partition of \(V(G)\) into subsets \(V_1, V_2,\dots, V_k\) such that for any \(i\) the subgraph of \(G\) induced by \(V_i\) contains a vertex adjacent to all other vertices of \(V_i\). A subset \(D \subseteq V(G)\) is a dominating set of \(G\) if any vertex in \(V(G) \setminus D\) is adjacent to a vertex of \(D\). The domination number of \(G\) is the smallest cardinality of any dominating set in \(G\). It is known that for a graph without isolated vertices \(G\), the smallest number of subsets of a star partition of \(G\) equals the domination number of \(G\). The paper investigates the Grundy chromatic number using the star partition of graphs. In particular, it provides upper bounds for the Grundy chromatic number that depend on the order, domination number, and length of the shortest cycle of general and triangle-free graphs.

Recommendations

• Bounds for the chromatic number of a graph
• Inequalities for the Grundy chromatic number of graphs
• BOUNDS ON THE DOMINATION NUMBER OF A GRAPH
• Results on the Grundy chromatic number of graphs
• On the Grundy and b-chromatic numbers of a graph
• scientific article; zbMATH DE number 2170337
• Bounds on the k-domination number of a graph
• On the dominated chromatic number of certain graphs
• Bounds to the chromatic polynomial of a graph
• Some bounds for the b-chromatic number of a graph

Cites work

• A new lower bound on the domination number of a graph
• First-fit colorings of graphs with no cycles of a prescribed even length
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Inequalities for the first-fit chromatic number
• Inequalities for the Grundy chromatic number of graphs
• Lower bounds for the domination number
• More bounds for the Grundy number of graphs
• New bounds for the chromatic number of graphs
• On the First-Fit 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
• Star partitions on graphs
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Cited in

(6)

• Inequalities between the domination number and the chromatic number of a graph
• Bounds for the chromatic number of graphs with partial information
• Bounds for the chromatic number of some \(pK_2\)-free graphs
• Upper bounds for some graph invariants in terms of blocks and cut-vertices
• Structural and spectral analysis of Fibonacci graphs and their Zagreb indices
• Grundy packing coloring of graphs

This page was built for publication: Bounds for the Grundy chromatic number of graphs in terms of domination number

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