(k, l)-colourings and Ferrers diagram representations of cographs. (January 2021)

• Record Type: Journal Article
• Authors: Epple, Dennis D.A.; Huang, Jing
• Is Part Of: European journal of combinatorics. Volume 91(2021)
• Publication Date: 2021-01
• Subjects: (k, l)-colouring -- Bichromatic number -- Ferrers diagram representation -- Cograph -- Algorithm -- Complexity; Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103208
• Languages: English
• ISSNs: 0195-6698

Abstract

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 .