7 papers
Obstructions for acyclic local tournament orientation completions
Kevin Hsu, Jing Huang
The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientatio…
(k; l)-Colourings and Ferrers Diagram Representations of Cographs
Dennis A. Epple, Jing Huang
For a pair of natural numbers , a -colouring of a graph is a partition of the vertex set of into (possibly empty) sets , $C_1, C_2, \dots…
Chordality of locally semicomplete and weakly quasi-transitive digraphs
Jing Huang, Ying Ying Ye
Chordal graphs are important in the structural and algorithmic graph theory. A digraph analogue of chordal graphs was introduced by Haskin and Rose in 1973 but has not been a subje…
Strongly chordal digraphs and -free matrices
Pavol Hell, Cesar Hernandez-Cruz, Jing Huang +1
We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to sq…
Comparability and Cocomparability Bigraphs
Pavol Hell, Jing Huang, Jephian C. -H. Lin +1
We propose bipartite analogues of comparability and cocomparability graphs. Surprizingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We char…
Interval-Like Graphs and Digraphs
Pavol Hell, Jing Huang, Ross M. McConnell +1
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include,…