(k, l)-colourings and Ferrers diagram representations of cographs. (January 2021) - Epple, Dennis D.A.; Huang, Jing
Abstract: For a pair of natural numbers k, l, a ( k, l ) -colouring of a graph G is a partition of the vertex set of G into (possibly empty) sets S 1, S 2, …, S k, C 1, C 2, …, C l such that each set S i is an independent set and each set C j induces a clique in G . The ( k, l ) -colouring problem, which is NP-complete in general, has been studied for special graph classes such as chordal graphs, cographs and line graphs. Let κ ˆ ( G ) = ( κ 0 ( G ), κ 1 ( G ), …, κ θ ( G ) − 1 ( G ) ) and λ ˆ ( G ) = ( λ 0 ( G ), λ 1 ( G ), …, λ χ ( G ) − 1 ( G ) ) where κ l ( G ) (respectively, λ k ( G ) ) is the minimum k (respectively, l ) such that G has a ( k, l ) -colouring. We prove that κ ˆ ( G ) and λ ˆ ( G ) are a pair of conjugate sequences for every graph G and when G is a cograph, the number of vertices in G is equal to the sum of the entries in κ ˆ ( G ) or in λ ˆ ( G ) . Using the decomposition property of cographs we show that every cograph can be represented by Ferrers diagram. We devise algorithms which compute κ ˆ ( G ) for cographs G and find an induced subgraph in G that can be used to certify the non- ( k, l ) -colourability of G .