A construction of uniquely colourable graphs with equal colour class sizes

DOI10.1016/J.DAM.2020.11.015MaRDI QIDQ1983120zbMATH OpenOpenAlexFDO

Authors S. Mohr

Publication date 15 September 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph colouringsuniquely colourable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A uniquely $k$-colourable graph is a graph with exactly one partition of the vertex set into at most $k$ colour classes. Here, we investigate some constructions of uniquely $k$-colourable graphs and give a construction of $K_k$-free uniquely $k$-colourable graphs with equal colour class sizes.

Recommendations

• Uniquely n-colorable and chromatically equivalent graphs
• Forcing structures and cliques in uniquely vertex colorable graphs
• scientific article; zbMATH DE number 4004207
• scientific article; zbMATH DE number 3924805
• Construction of uniquely vertex k-colorable graphs with minimum possible size

Cites work

• scientific article; zbMATH DE number 3405977 (Why is no real title available?)
• On uniquely colorable planar graphs
• The size of uniquely colorable graphs
• Tiling Turán theorems
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Uniquely Colourable Graphs with Large Girth
• Uniquely colorable graphs
• \(K_r\)-free uniquely vertex colorable graphs with minimum possible edges

Cited in

(5)

• scientific article; zbMATH DE number 4041944 (Why is no real title available?)
• scientific article; zbMATH DE number 3966100 (Why is no real title available?)
• The size of uniquely colorable graphs
• scientific article; zbMATH DE number 4004207 (Why is no real title available?)
• Construction of uniquely vertex k-colorable graphs with minimum possible size

This page was built for publication: A construction of uniquely colourable graphs with equal colour class sizes

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