In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

area of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a graph is even-hole-free if it contains no

induced cycle In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an ...

with an even number of vertices. More precisely, the definition may allow the graph to have induced cycles of length four, or may also disallow them: the latter is referred to as even-cycle-free graphs. demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.

Recognition

gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in

(n^)

time. later improved this to

(n^)

. and improved this to

(n^)

time. The best currently known algorithm is given by which runs in

(n^9)

time. While even-hole-free graphs can be recognized in polynomial time, it is NP-complete to determine whether a graph contains an even hole that includes a specific vertex. It is unknown whether

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

and the

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

problem can be solved in polynomial time on even-hole-free graphs, or whether they are NP-complete. However the

maximum clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complet ...

can be found in even-hole-free graphs in polynomial time.

Notes

References

* * * * * * * * * *

External links

* {{citation , contribution-url = http://www.graphclasses.org/classes/gc_547.html , contribution = Even-hole-free graphs , url = http://www.graphclasses.org/index.html , title = Information System on Graph Classes and their Inclusions Graph families