Maximal ambiguously \(k\)-colorable graphs (Q2284731)

Chromatic study of graphs is an important area of graph theory and possibly contains one of the oldest problems related to graphs, namely 4-color problem. There are many types of coloring of graphs. In this paper, the author studied the ambiguously \(k\)-colorable graphs which are related to the Hadwiger's and Seymour conjectures. Using square matrices of dimension \(k\), he gave a full characterization of the maximal ambiguously \(k\)-colorable graphs. The results obtained are applied to determine the maximum number of edges an ambiguously \(k\)-colorable graph can have.