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

DOI10.1007/978-3-031-38906-1_36MaRDI QIDQ6139034zbMATH OpenOpenAlexFDO

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

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Can they cross? and how? (the hitchhiker's guide to the universe of geometric intersection graphs)
• 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
• Open problems on graph coloring for special graph classes
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• The complexity of colouring problems on dense graphs
• The complexity of surjective homomorphism problems-a survey
• The strong perfect graph theorem
• Three complexity results on coloring \(P_k\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cited in

(1)

• \(C_{2k+1}\)-coloring of bounded-diameter 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)