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

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

Authors: 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? (the hitchhiker's guide to the universe of geometric intersection graphs)

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)