BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for every n, there is a graph G with χ(G)≥n and ω(G)≤3 such that every induced subgraph H of G with ω(H)≤2 satisfies χ(H)≤4. This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5.
Let H and G be graphs such that H has at least 3 vertices and is connected. The H-line graph of G, denoted by HL(G), is that graph whose vertices are the edges of G and where two vertices of HL(G) are adjacent if they are adjacent in G and lie in a common copy of H. For each nonnegative integer k, let HLk(G) denote the k-th iteration of the H-line graph of G. We say that the sequence {HLk(G)} converges if there exists a positive integer N such that HLk(G)≅HLk+1(G), and for n≥3 we set Λn as the set of all graphs G whose sequence {HLk(G)} converges when H≅Pn. The sets Λ3,Λ4 and Λ5 have been characterized. To progress towards the characterization of Λn in general, this paper defines and studies the following property: a graph G is minimally n-convergent if G∈Λn but no proper subgraph of G is in Λn. In addition, prove conditions that imply divergence, and use these results to develop some of the properties of minimally n-convergent graphs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.