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

DOI10.1016/J.DISC.2016.03.011MaRDI QIDQ284759zbMATH OpenOpenAlexFDO

Authors Brice Effantin, Nicolas Gastineau, Olivier Togni

Publication date 18 May 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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

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

Cites work

• scientific article; zbMATH DE number 5717278 (Why is no real title available?)
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• scientific article; zbMATH DE number 1919512 (Why is no real title available?)
• A characterization of \(b\)-perfect graphs
• Bounds for the b-chromatic number of G-v
• Characterization of some \(b\)-chromatic edge critical graphs
• Graphs of girth at least 7 have high \(b\)-chromatic number
• Modular representations of Loewy length two.
• On edge-\(b\)-critical graphs
• On minimally \(b\)-imperfect graphs
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• On the \(b\)-coloring of \(G - e\)
• On the \(b\)-continuity property of graphs
• On vertex \(b\)-critical trees
• On-line 3-chromatic graphs. II: Critical graphs
• Results on the Grundy chromatic number of graphs
• The b-chromatic number of a graph
• The b-chromatic number of cubic graphs
• \(b\)-coloring of some bipartite graphs
• \(b\)-coloring of tight graphs
• \(b\)-colouring the Cartesian product of trees and some other 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)