Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
From MaRDI portal
Publication:2167905
DOI10.1016/j.tcs.2022.07.034OpenAlexW3216791769MaRDI QIDQ2167905
Daniël Paulusma, Barnaby Martin, Siani Smith
Publication date: 1 September 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2111.11897
Cites Work
- Unnamed Item
- 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
- Vertex coloring of graphs with few obstructions
- The complexity of surjective homomorphism problems-a survey
- 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
- Quasi-claw-free 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
- Hard problems that quickly become very easy
- Colouring \((P_r + P_s)\)-free graphs
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Coloring graphs without short cycles and long induced paths
- Hard coloring problems in low degree planar bipartite 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
- Filling the complexity gaps for colouring planar and bounded degree graphs
- 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
- Almost claw‐free graphs
- NP completeness of finding the chromatic index of regular graphs
- Colouring H-free graphs of bounded diameter.
- Four-coloring P6-free graphs
- The complexity of satisfiability problems
- There is No Irregular Moore Graph
- Colouring graphs of bounded diameter in the absence of small cycles
- Acyclic, star, and injective colouring: bounding the diameter
- Acyclic, star, and injective colouring: bounding the diameter
This page was built for publication: Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
