A construction of uniquely colourable graphs with equal colour class sizes

DOI10.1016/J.DAM.2020.11.015zbMATH Open1472.05058arXiv2001.08801OpenAlexW3002248244MaRDI QIDQ1983120FDOQ1983120

S. Mohr

Publication date: 15 September 2021

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

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.

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

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

zbMATH Keywords

graph colouringsuniquely colourable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Tiling Turán theorems
• Uniquely Colourable Graphs with Large Girth
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Uniquely colorable graphs
• The size of uniquely colorable graphs
• On uniquely colorable planar graphs
• Title not available (Why is that?)
• \(K_r\)-free uniquely vertex colorable graphs with minimum possible edges

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• The size of uniquely colorable graphs
• Title not available (Why is that?)
• 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)