On line graphs of linear 3-uniform hypergraphs
The line graph of a hypergraph \(H\) is the intersection graph of the edges of \(H\). \(H\) is called linear if any two edges have at most one common vertex, and a hypergraph whose edge degrees are all equal to \(r\) is called \(r\)-uniform. Let the classes of line graphs of \(r\)-uniform hypergraphs and of linear \(r\)-uniform hypergraphs be denoted by \(L_r\) and \(L^1_r\), respectively. This means that \(L^1_2\) is the class of line graphs of simple graphs. Necessary and sufficient conditions of Krausz and Beineke for \(G\) being a member of \(L^1_2\) are already known. Lovász noted that the class \(L_3\) cannot be characterized by a finite list of forbidden induced subgraphs. Further it is known that such a characterization is also impossible for the class \(L^1_3\). The results of the present paper can be summarized in the following manner: (1) A finite induced subgraph characterization of graphs in \(L^1_3\) whose vertex degrees are at least 19 is given (Theorem 3.1). Also the finite list of forbidden subgraphs is given. The proof is based on the above-mentioned results of Krausz and Beineke, on former results of other authors, and by using some propositions of the present paper. (2) In connection with these investigations the authors also found an analogous characterization of graphs in \(L^1_2\) with vertex degrees at least 5 (Theorem 3.2). (3) In case \(r>3\) and an arbitrary constant \(c\), the set of graphs in \(L^1_r\) whose vertex degrees are at least \(c\) cannot be characterized by a finite list of forbidden induced subgraphs (Theorem 3.3). (4) The algorithm for the recognition problem \(G\in L^1_3\) with vertex degree at least 19 is described, and this procedure has polynomial complexity (a polynomial in the number of vertices).
- On automorphisms of line-graphs
- Recognizing intersection graphs of linear uniform hypergraphs
- Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
- Lower bounds on Tuza constants for transversals in linear uniform hypergraphs
- The strong intersecting number of a graph
- On uniform linear hypergraph set-indexers of a graph
- On the problem of domino recognition
- scientific article; zbMATH DE number 6503350 (Why is no real title available?)
- Graphs as r-minoes
- On the size of 3-uniform linear hypergraphs
- scientific article; zbMATH DE number 123325 (Why is no real title available?)
- Line Graphs of Helly Hypergraphs
- scientific article; zbMATH DE number 6863845 (Why is no real title available?)
- scientific article; zbMATH DE number 2107052 (Why is no real title available?)
- A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs
- scientific article; zbMATH DE number 7325727 (Why is no real title available?)
- Edge intersection graphs of linear 3-uniform hypergraphs
- Edge intersection graphs of linear 3-uniform hypergraphs
- On 3-uniform hypergraphs without linear cycles
- \((k-2)\)-linear connected components in hypergraphs of rank \(k\)
- Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth
This page was built for publication: On line graphs of linear 3-uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4351311)
