Premium
Interval bigraphs and circular arc graphs
Author(s) -
Hell Pavol,
Huang Jing
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20006
Subject(s) - combinatorics , mathematics , interval graph , chordal graph , indifference graph , bipartite graph , cograph , conjecture , discrete mathematics , split graph , permutation graph , vertex (graph theory) , interval (graph theory) , graph , 1 planar graph
We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that we hope may prove helpful in finding a more efficient recognition algorithm than presently known. We use these results to show equality, amongst bipartite graphs, of several classes of structured graphs (proper interval bigraphs, complements of proper circular arc graphs, asteroidal‐triple‐free graphs, permutation graphs, and co‐comparability graphs). Our results verify a conjecture of Lundgren and disprove a conjecture of Müller. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 313–327, 2004