Hajós-like theorem for signed graphs

2017/02/27 by Yingli Kang, Kang, Yingli
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1702.08232

Abstract

The paper designs five graph operations, and proves that every signed graph with chromatic number q can be obtained from all-positive complete graphs (K_q,+) by repeatedly applying these operations. This result gives a signed version of the Hajós theorem, emphasizing the role of all-positive complete graphs played in the class of signed graphs, as played in the class of unsigned graphs.

Related

• On the signed chromatic number of some classes of graphs
• The Chromatic Number of Joins of Signed Graphs
• On the 4-color theorem for signed graphs
• Degree choosable signed graphs
• Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs