Colouring graphs of bounded diameter in the absence of small cycles

DOI10.1007/978-3-030-75242-2_26OpenAlexW3164098456MaRDI QIDQ5925681

Siani Smith, Daniël Paulusma, Barnaby Martin

Publication date: 22 March 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_26

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (3)

Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Faster 3-Coloring of Small-Diameter Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Vertex coloring of graphs with few obstructions
• The complexity of surjective homomorphism problems-a survey
• The complexity of colouring problems on dense graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Vertex colouring and forbidden subgraphs -- a survey
• Three complexity results on coloring \(P_k\)-free graphs
• Coloring graphs without short cycles and long induced paths
• Open Problems on Graph Coloring for Special Graph Classes
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• On Moore Graphs with Diameters 2 and 3
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Colouring (P_r+P_s)-Free Graphs
• Colouring H-free graphs of bounded diameter.
• The complexity of satisfiability problems

This page was built for publication: Colouring graphs of bounded diameter in the absence of small cycles