Research On Cocomparability Graphs And Comparability Digraphs

Comparability graphs are graphs that represent the comparability relation of partial orders.Cocomparability graphs are the complement graphs of comparabil-ity graphs.Comparability graphs,cocomparability graphs and partial orders have a natural one-to-one correspondence.Lexicographic Breath First Search（LBFS）was first introduced by Rose,Tarjan,and Lueker for recognizing chordal graphs.LBFS⁺is a variant of LBFS,which uses a specific tie-breaking mechanism.Start-ing with some orderingσ₀of G,let{σ_i}_i≥1be the sequence of orderings such thatσ_i=LBFS⁺(G,σ_i-1).The Lex Cycle（G）of a graph G is defined as the maximum length of a cycle of vertex orderings of G obtained via such a sequence of LBFS⁺sweeps.Lexicographic Depth First Search（LDFS）also plays an important role in recognizing several graph classes.The minimum path cover（MPC）problem is to find a minimum vertex disjoint path set P in the graph,such that each vertex is in exactly one path of P.This problem covers the Hamiltonian path problem.In this paper,we mainly study Lex Cycle and the minimum path cover problem for undirected cocomparability graphs.Let D=（V,A）be a digraph.D is called a comparability digraph if there exists a vertex ordering＜of D,so that for any x＜y＜z or z＜y＜x,if xy,yz∈A,then xz∈A.D is called an interval digraph,if D has an interval pair representation,that is,for each vertex v∈V,there exists a set of interval pairs I_v,J_v,such that uv∈A if and only if I_uand J_vintersect.Further,Feder et al.introduced a new class of digraphs:adjusted interval digraphs.D is called an adjusted interval digraph,if D is an interval digraph and its interval pair representation satisfies that I_v,J_vhave the same left endpoint for each vertex v of D.In this paper,we study the characterizations of（semi-complete）comparability digraphs and（semi-complete）adjusted interval digraphs.This paper contains five chapters.In chapter 1,we first give some basic concepts,terminology and notation needed in this paper;then we introduce the research background and related research progress;finally,we give the main results in this paper.In chapter 2,we study the Lex Cycle and the minimum path cover（MPC）problem of undirected cocomparability graphs.Dusart and Habib conjectured that Lex Cycle（G）=2 if G is a cocomparability graph,and Charbit et al.proved it holds for several subclasses of cocomparability graphs（such as proper inter-val graphs,interval graphs,co-bipartite graphs and domino-free cocomparability graphs）and trees.We consider （?）-free cocomparability graphs,where a （?）is the graph whose complement is the disjoint union of P₂and P₃.Obvi-ously,this graph class strictly contain interval graphs as subgraphs.We show that Lex Cycle（G）=2 if G is a （?）-free cocomparability graph.Secondly,for the MPC problem,Corneil gave in 2013 an LDFS-based certifying algorithm called MPC-COCOMP for the MPC problem on cocomparability graphs,where the al-gorithm itself is correct while the proof is incomplete.In this paper,we give a complete and easy proof of it.In chapter 3,we study a class of digraphs analogous to comparability graphs:comparability digraphs.In this paper,we first introduce the knotting graphK_Dof a digraph D and the implication class of D,and then obtain the close relationship between the implication classes of D and the components of the knotting graphK_Dof D.Further,we give a characterization on comparability digraphs D by usingK_D:A digraph D is a comparability digraph if and only ifK_Dis bipartite and there exists a bipartition（X,Y）ofK_Dsuch that the orientation ofK_Dfrom X to Y transforms into an acyclic orientation of U（D）.In general,it’s not clear whether these digraphs can be recognized in polynomial time.In chapter 4,we focus on semi-complete comparability digraphs which are also a prototype of comparability graphs,and generalize the Triangle Lemma to semi-complete digraphs.Using the Triangle Lemma for semi-complete digraphs we prove that if an implication class of a semi-complete digraph contains no circuit of length 2 then it contains no circuit at all.We also use it to device an O（n~3）time recognition algorithm for semi-complete comparability digraphs where n is the number of vertices of the input digraph.The correctness of the algorithm implies a characterization for semi-complete comparability digraphs,akin to that for comparability graphs.In chapter 5,we study adjusted interval digraphs and semi-complete adjusted interval digraphs.We introduce cocomparability digraphs and show that adjusted interval digraphs are strictly contained in the intersection of chordal digraphs and cocomparability digraphs.Then we introduce a notation analogous to the usual maximal cliques:maximal quasi-cliques,and give a characterization of adjusted interval digraphs by using this parameter.Further,we specify this characteriza-tion by combining the characterization of undirected interval graphs.Further,we introduce a forbidden structure and obtain some properties and characterizations on semi-complete adjusted interval digraphs.