More bounds for the Grundy number of graphs

DOI10.1007/S10878-015-9981-8MaRDI QIDQ511707zbMATH OpenOpenAlexWikidataFDO

Authors Zixing Tang, Baoyindureng Wu, Lin Hu, Manoucheher Zaker

Publication date 22 February 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberclique numberGrundy numbercoloring numberRandić index

Mathematics Subject Classification ID

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

Abstract: A coloring of a graph $G=(V,E)$ is a partition $V_1,V_2,ldots,V_k$ of $V$ into independent sets or color classes. A vertex $vin{V}_i$ is a Grundy vertex if it is adjacent to at least one vertex in each color class $V_j$ for every $j<i$. A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number $Gamma(G)$ of a graph $G$ is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a $P_4,C_4$-free graph by supporting a conjecture of Zaker, which says that $Gamma(G)geqdelta(G)+1$ for any $C_4$-free graph $G$.

Recommendations

• New bounds on the Grundy number of products of graphs
• Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs
• Inequalities for the Grundy chromatic number of graphs
• On the Grundy number of graphs with few P₄'s
• Grundy numbers of products of paths, cycles, and stars

Cites work

• scientific article; zbMATH DE number 2147949 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 5251354 (Why is no real title available?)
• scientific article; zbMATH DE number 3253789 (Why is no real title available?)
• A proof for a conjecture on the Randić index of graphs with diameter
• A survey of Nordhaus-Gaddum type relations
• Chromatic graph theory
• First-fit chromatic numbers of \(d\)-degenerate graphs
• First-fit colorings of graphs with no cycles of a prescribed even length
• Graphs of extremal weights
• Grundy number and products of graphs
• Grundy number of graphs
• Inequalities for the Grundy chromatic number of graphs
• Inequalities for the first-fit chromatic number
• New bounds for the chromatic number of graphs
• On Complementary Graphs
• On a relation between the Randić index and the chromatic number
• On rigid circuit graphs
• On the conjecture of Aouchiche and Hansen about the Randić index
• On the family of \(r\)-regular graphs with Grundy number \(r+1\)
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Ordered colourings of graphs
• Proof of the first part of the conjecture of Aouchiche and Hansen about the Randić index
• Randić index and coloring number of a graph
• Results on the Grundy chromatic number of graphs
• Series expansion of the directed percolation probability
• Some perfect coloring properties of graphs
• The Comparability Graph of a Tree
• The achromatic number of a graph
• Trivially perfect graphs
• -perfect graphs

Cited in

(13)

• Inequalities for the Grundy chromatic number of graphs
• A note on Grundy colorings of central graphs
• Grundy Distinguishes Treewidth from Pathwidth
• \(\mathcal{O}(VE)\) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth
• Bounds for the Grundy chromatic number of graphs in terms of domination number
• A four colorings theorem
• On the family of \(r\)-regular graphs with Grundy number \(r+1\)
• On the geometric-arithmetic index of a graph
• Grundy distinguishes treewidth from pathwidth
• Spectral upper bounds for the Grundy number of a graph
• scientific article; zbMATH DE number 7034391 (Why is no real title available?)
• Upper bounds for some graph invariants in terms of blocks and cut-vertices
• Grundy number of graphs

This page was built for publication: More bounds for the Grundy number of graphs

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