On \(b\)-greedy colourings and \(z\)-colourings

DOI10.1016/j.dam.2024.08.001MaRDI QIDQ6633541

Jonas Costa Ferreira da Silva, Frédéric Havet

Publication date: 6 November 2024

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

zbMATH Keywords

cubic graphNP-hardness\(b\)-colouringgreedy colouring\(z\)-colouring

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-fit coloring on interval graphs has performance ratio at least 5
• The b-chromatic number of cubic graphs
• Results on the Grundy chromatic number of graphs
• Grundy number and products of graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• The b-chromatic number of a graph
• The \(b\)-chromatic number and related topics -- a survey
• On the Grundy and \(b\)-chromatic numbers of a graph
• On the Nash number and the diminishing Grundy number of a graph
• A new vertex coloring heuristic and corresponding chromatic number
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-chromatic number of regular bounded graphs
• On the family of \(r\)-regular graphs with Grundy number \(r+1\)
• Bounds for the b-chromatic number of some families of graphs
• Reducibility among Combinatorial Problems
• More results on the \(z\)-chromatic number of graphs

This page was built for publication: On \(b\)-greedy colourings and \(z\)-colourings