A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

DOI10.1016/J.DISC.2016.03.011zbMATH Open1337.05040arXiv1505.07780OpenAlexW1930585892MaRDI QIDQ284759FDOQ284759

Authors: Brice Effantin, Nicolas Gastineau, Olivier Togni 

Publication date: 18 May 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Gy{'a}rf{'a}s et al. and Zaker have proven that the Grundy number of a graph $G$ satisfies $Gamma(G)get$ if and only if $G$ contains an induced subgraph called a $t$-atom.The family of $t$-atoms has bounded order and contains a finite number of graphs.In this article, we introduce equivalents of $t$-atoms for b-coloring and partial Grundy coloring.This concept is used to prove that determining if $varphi(G)get$ and $partialGamma(G)get$ (under conditions for the b-coloring), for a graph $G$, is in XP with parameter $t$.We illustrate the utility of the concept of $t$-atoms by giving results on b-critical vertices and edges, on b-perfect graphs and on graphs of girth at least $7$.

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

Recommendations

• Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs
• On the Grundy and \(b\)-chromatic numbers of a graph
• On the equality of the partial Grundy and upper ochromatic numbers of graphs
• Discussion on the (partial)Grundy and b-chromatic numbers of graphs
• \(b\)-continuity and partial Grundy coloring of graphs with large girth

zbMATH Keywords

parameterized complexity\(b\)-coloringGrundy numberpartial Grundy number

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• The b-chromatic number of a graph
• On-line 3-chromatic graphs. II: Critical graphs
• \(b\)-coloring of tight graphs
• Modular representations of Loewy length two.
• \(b\)-colouring the Cartesian product of trees and some other graphs
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-coloring of \(G - e\)
• Graphs of girth at least 7 have high \(b\)-chromatic number
• On the \(b\)-continuity property of graphs
• On vertex \(b\)-critical trees
• \(b\)-coloring of some bipartite graphs
• A characterization of \(b\)-perfect graphs
• Title not available (Why is that?)
• Bounds for the \(b\)-chromatic number of \(G-v\)
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• Title not available (Why is that?)
• Title not available (Why is that?)
• On edge-\(b\)-critical graphs
• Characterization of some \(b\)-chromatic edge critical graphs
• The b-chromatic number of cubic graphs
• Results on the Grundy chromatic number of graphs
• On minimally \(b\)-imperfect graphs

Cited In (11)

• Grundy Coloring and friends, half-graphs, bicliques
• \(b\)-coloring parameterized by clique-width
• On the parameterized complexity of b-\textsc{chromatic number}
• Spectral upper bounds for the Grundy number of a graph
• A comparison of the Grundy and b-chromatic number of \(K_{2,t}\)-free graphs
• More results on the \(z\)-chromatic number of graphs
• A note on induced subtrees and chromatic number of graphs
• A new vertex coloring heuristic and corresponding chromatic number
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
• Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs
• On Grundy and b-chromatic number of some families of graphs: a comparative study

This page was built for publication: A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs

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