The complexity of frugal colouring

DOI10.1007/s40065-021-00311-7zbMath1462.05131OpenAlexW3128824031MaRDI QIDQ2023759

Gary MacGillivray, Stefan Bard, Shayla Redlin

Publication date: 3 May 2021

Published in: Arabian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40065-021-00311-7

zbMATH Keywords

complexitygraph colouringlocally injective colouring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Injective coloring of plane graphs with girth 5
• Locally injective \(k\)-colourings of planar graphs
• List injective colorings of planar graphs
• Frugal, acyclic and star colourings of graphs
• The distance coloring of graphs
• Asymptotically optimal frugal colouring
• Colouring a graph frugally
• Coloring the square of a \(K_{4}\)-minor free graph
• The square of a planar cubic graph is 7-colorable
• On the injective chromatic number of graphs
• A survey on the distance-colouring of graphs
• A bound on the chromatic number of the square of a planar graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• List Colouring Squares of Planar Graphs
• List-Coloring Squares of Sparse Subcubic Graphs
• Labelling Graphs with a Condition at Distance 2
• Complexity of locally-injective homomorphisms to tournaments
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• On Injective Colourings of Chordal Graphs
• Injective coloring of planar graphs

This page was built for publication: The complexity of frugal colouring