More bounds for the Grundy number of graphs

DOI10.1007/S10878-015-9981-8zbMATH Open1359.05048arXiv1507.01080OpenAlexW2218870702WikidataQ130405903 ScholiaQ130405903MaRDI QIDQ511707FDOQ511707

Manoucheher Zaker, Lin Hu, Baoyindureng Wu, Zixing Tang

Publication date: 22 February 2017

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

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$.

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

zbMATH Keywords

chromatic number[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Randi%EF%BF%BD%EF%BF%BD+index&go=Go Randi�� index]clique numberGrundy numbercoloring number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Grundy Distinguishes Treewidth from Pathwidth
• Title not available (Why is that?)
• Bounds for the Grundy chromatic number of graphs in terms of domination number
• On the geometric-arithmetic index of a graph
• Title not available (Why is that?)
• 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)