4 citations · 6 across the 14 of their papers we have counts for
16 papers
The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs
Shamik Ghosh, Jing Huang
A digraph is 3-transitive (respectively, 3-quasi-transitive) if whenever is a directed path of length 3, (respectively, or $(z,u…
Gallai-like characterization of strong cocomparability graphs
Jing Huang
Strong cocomparability graphs are the reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows $01, 1…
Strong cocomparability graphs and Slash-free orderings of matrices
Pavol Hell, Jing Huang, Jephian C. -H. Lin
We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to a…
Semi-strict chordality of digraphs
Jing Huang, Ying Ying Ye
Chordal graphs are important in algorithmic graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. Unlike chord…
Comparability digraphs: An analogue of comparability graphs
Xiao-Lu Gao, Jing Huang, Shou-Jun Xu
Comparability graphs are a popular class of graphs. We introduce as the digraph analogue of comparability graphs the class of comparability digraphs. We show that many concepts suc…
Obstructions for local tournament orientation completions
Kevin Hsu, Jing Huang
The orientation completion problem for a class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class by orienting the…
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,…
Further results on the expected hitting time, the cover cost and the related invariants of graphs
Jing Huang, Shuchao Li, Zheng Xie
A close relation between hitting times of the simple random walk on a graph, the Kirchhoff index, resistance-centrality, and related invariants of unicyclic graphs is displayed. Co…
Relation between the skew-rank of an oriented graph and the independence number of its underlying graph
J. Huang, S. C. Li, H. Wang
An oriented graph is a digraph without loops or multiple arcs whose underlying graph is . Let be the skew-adjacency matrix of and be the i…
End-vertices of LBFS of (AT-free) bigraphs
Jan Gorzny, Jing Huang
Lexicographic Breadth First Search (LBFS) is one of fundamental graph search algorithms that has numerous applications, including recognition of graph classes, computation of graph…
Completing orientations of partially oriented graphs
Joergen Bang-Jensen, J. Huang, Xuding Zhu
We initiate a general study of what we call orientation completion problems. For a fixed class C of oriented graphs, the orientation completion problem asks whether a given partial…