Graphclass: line

The following definitions are equivalent:
  1. The line graph (E,E') of G = (V,E) has edges (e,f) if e\cap f isn't empty in G.
    A graph is a line graph if it is the line graph of some graph.
  2. A graph G is a line graph if the edges of G can be partitioned into maximal complete subgraphs such that no vertex lies in more than two of the subgraphs.
  3. A triangle T of a graph G is called odd if there is a vertex of G that is adjacent to an odd number of vertices of T.
    A graph G is a line graph if G is claw-free and if two odd triangles have a common edge, then the subgraph induced by their vertices is a K4 .

References

[77]
L.W. Beineke
On derived graphs and digraphs
Beitr. Graphentheorie, Int. Kolloquium Manebach (DDR) 1967, 17-23 (1968).
[78]
L.W. Beineke
Characterization of derived graphs
J. Comb. Theory 9 1970 129--135
[700]
J. Krausz
D\'emonstration nouvelle d'une th\'eor\`eme de Whitney sur les r\'eseaux
Math. Fiz. Lapok 50 1943 75--85
[1065]
A. Van Rooij, H. Wilf
The interchange of a finite graph
Acta Math. Acad. Sci. Hung. 16 1965 263--269

;

[719]
P.G.H. Lehot
An optimal algorithm to detect a line graph and output its root graph
J. ACM 21 1974 569--575
[934]
D. Rotem, J. Urrutia
Circular permutation graphs
% {\sl Res. Rep. Univ. Waterloo} 0
[1129]
M. Yannakakis, F. Gavril
Edge dominating sets in graphs
SIAM J. Appl. Math. 38(3) 364-372, 1980
[1432]
I. Holyer
The NP-completeness of edge-coloring
SIAM J. Computing 10 718-720 (1981)
[1521]
A.A. Bertossi
The edge Hamiltonian path problem is NP-complete
Information Proc. Lett. 13 157-159 (1981)
[1678]
V. Guruswami
Maximum cut on line and total graphs
Discrete Appl. Math. 92 217-221 (1999)
[1688]
V.N. Zemlyachenko, N.M. Korneenko, R.I. Tyshkevich
Graph isomorphism problem
J. of Soviet Mathematics 29 No.4 1426-1481

Equivalent classes

[+]Details

Complement classes

Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

Map

[+]Details

Minimal superclasses

[+]Details

Maximal subclasses

[+]Details

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.

3-Colourability
[?]
Input: A graph G in this class.
Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.
NP-complete [+]Details
Clique
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.
Polynomial [+]Details
Clique cover
[?]
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.
Unknown to ISGCI [+]Details
Cliquewidth
[?]
Whether the cliquewidth of the graphs in this class is bounded by a constant k .
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:
  • creation of a vertex with label i,
  • disjoint union,
  • renaming labels i to label j,
  • connecting all vertices with label i to all vertices with label j.
Unbounded [+]Details
Cliquewidth expression
[?]
Input: A graph G in this class.
Output: An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels.
Undefined if this class has unbounded cliquewidth.
Unbounded or NP-complete [+]Details
Colourability
[?]
Input: A graph G in this class and an integer k.
Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.
NP-complete [+]Details
Cutwidth
[?]
Input: A graph G in this class and an integer k.
Output: True iff the cutwidth of G is at most k (see bounded cutwidth).
Unknown to ISGCI [+]Details
Domination
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
NP-complete [+]Details
Feedback vertex set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.
Unknown to ISGCI [+]Details
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
GI-complete [+]Details
Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
NP-complete [+]Details
Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
NP-complete [+]Details
Independent dominating set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
Polynomial [+]Details
Independent set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.
Polynomial [+]Details
Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
Polynomial [+]Details
Recognition
[?]
Input: A graph G.
Output: True iff G is in this graph class.
Linear [+]Details
Treewidth
[?]
Input: A graph G in this class and an integer k.
Output: True iff the treewidth of G is at most k (see bounded treewidth).
Unknown to ISGCI [+]Details
Weighted clique
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
Polynomial [+]Details
Weighted feedback vertex set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.
Unknown to ISGCI [+]Details
Weighted independent dominating set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.
Polynomial [+]Details
Weighted independent set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
Polynomial [+]Details
Weighted maximum cut
[?]
(decision variant)
Input: A graph G in this class with weight function on the edges and a real k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that the sum of weights of the edges in G with one endpoint in A and the other endpoint in B is at least k.
NP-complete [+]Details