3-coloring C₄ or C₃-free diameter two graphs

DOI10.1007/978-3-031-38906-1_36arXiv2307.15036OpenAlexW4385357272MaRDI QIDQ6139034FDOQ6139034

Tereza Klimošová, Vibha Sahlot

Publication date: 16 January 2024

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

Full work available at URL: https://arxiv.org/abs/2307.15036

zbMATH Keywords

3-coloringdiameter 2 graphsinduced \(C_3\) free graphsinduced \(C_4\) free graphslist 3-coloring

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites Work

• Reducibility among Combinatorial Problems
• The complexity of colouring problems on dense graphs
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• The complexity of surjective homomorphism problems-a survey
• Title not available (Why is that?)
• The strong perfect graph theorem
• Some simplified NP-complete graph problems
• Open Problems on Graph Coloring for Special Graph Classes
• Three complexity results on coloring \(P_k\)-free graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Colouring H-free graphs of bounded diameter.
• Colouring graphs of bounded diameter in the absence of small cycles
• Faster 3-Coloring of Small-Diameter Graphs
• Can they cross? and how?

This page was built for publication: 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139034)