Colouring H-free graphs of bounded diameter.

DOI10.4230/LIPIcs.MFCS.2019.14OpenAlexW2968066320MaRDI QIDQ5092372

Barnaby Martin, Siani Smith, Daniël Paulusma

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.14

zbMATH Keywords

diametervertex colouring\(H\)-free graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (11)

Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Hard problems that quickly become very easy ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs

Cites Work

• Unnamed Item
• 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
• Colouring graphs when the number of colours is almost the maximum degree
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• 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
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Hard coloring problems in low degree planar bipartite graphs
• Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
• 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
• NP completeness of finding the chromatic index of regular graphs
• Colouring (P_r+P_s)-Free Graphs
• Four-coloring P₆-free graphs
• The complexity of satisfiability problems
• There is No Irregular Moore Graph

This page was built for publication: Colouring H-free graphs of bounded diameter.