Meyniel graph

Last updated
In a Meyniel graph, every long odd cycle (such as the black 5-cycle shown here) must have at least two chords (green) Chordal-graph.svg
In a Meyniel graph, every long odd cycle (such as the black 5-cycle shown here) must have at least two chords (green)

In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords, edges connecting non-consecutive vertices of the cycle. [1] The chords may be uncrossed (as shown in the figure) or they may cross each other, as long as there are at least two of them.

Contents

The Meyniel graphs are named after Henri Meyniel (also known for Meyniel's conjecture), who proved that they are perfect graphs in 1976, [2] long before the proof of the strong perfect graph theorem completely characterized the perfect graphs. The same result was independently discovered by Markosjan & Karapetjan (1976). [3]

Perfection

The Meyniel graphs are a subclass of the perfect graphs. Every induced subgraph of a Meyniel graph is another Meyniel graph, and in every Meyniel graph the size of a maximum clique equals the minimum number of colors needed in a graph coloring. Thus, the Meyniel graphs meet the definition of being a perfect graph, that the clique number equals the chromatic number in every induced subgraph. [1] [2] [3]

Meyniel graphs are also called the very strongly perfect graphs, because (as Meyniel conjectured and Hoàng proved) they can be characterized by a property generalizing the defining property of the strongly perfect graphs: in every induced subgraph of a Meyniel graph, every vertex belongs to an independent set that intersects every maximal clique. [1] [4]

The Meyniel graphs contain the chordal graphs, the parity graphs, and their subclasses the interval graphs, distance-hereditary graphs, bipartite graphs, and line perfect graphs. [1]

The house graph is perfect but not Meyniel House graph.svg
The house graph is perfect but not Meyniel

Although Meyniel graphs form a very general subclass of the perfect graphs, they do not include all perfect graphs. For instance the house graph (a pentagon with only one chord) is perfect but is not a Meyniel graph.

Algorithms and complexity

Meyniel graphs can be recognized in polynomial time, [5] and several graph optimization problems including graph coloring that are NP-hard for arbitrary graphs can be solved in polynomial time for Meyniel graphs. [6] [7]

Related Research Articles

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k−1 independent sets.

Chordal graph Graph family

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

Grundy number

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.

Distance-hereditary graph

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

Clique-sum

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have at most k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation.

Greedy coloring One-by-one assignment of colors to graph vertices

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

Block graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

Skew partition

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

Paul Allen Catlin was a mathematician, professor of mathematics who worked in graph theory and number theory. He wrote a significant paper on the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

Cluster graph

In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called P3-free graphs. They are the complement graphs of the complete multipartite graphs and the 2-leaf powers.

Well-colored graph

In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for its vertices. That is, for these graphs, the chromatic number and Grundy number are equal.

References

  1. 1 2 3 4 Meyniel graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
  2. 1 2 Meyniel, H. (1976), "On the perfect graph conjecture", Discrete Mathematics , 16 (4): 339–342, doi: 10.1016/S0012-365X(76)80008-8 , MR   0439682 .
  3. 1 2 Markosjan, S. E.; Karapetjan, I. A. (1976), "Perfect graphs", Doklady Akademiya Nauk Armyanskoĭ SSR, 63 (5): 292–296, MR   0450130 .
  4. ↑ Hoàng, C. T. (1987), "On a conjecture of Meyniel", Journal of Combinatorial Theory , Series B, 42 (3): 302–312, doi: 10.1016/0095-8956(87)90047-5 , MR   0888682 .
  5. ↑ Burlet, M.; Fonlupt, J. (1984), "Polynomial algorithm to recognize a Meyniel graph", Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam, pp. 225–252, doi:10.1016/S0304-0208(08)72938-4, hdl: 10068/49205 , MR   0778765 .
  6. ↑ Hertz, A. (1990), "A fast algorithm for coloring Meyniel graphs", Journal of Combinatorial Theory , Series B, 50 (2): 231–240, doi: 10.1016/0095-8956(90)90078-E , MR   1081227 .
  7. ↑ Roussel, F.; Rusu, I. (2001), "An O(n2) algorithm to color Meyniel graphs", Discrete Mathematics , 235 (1–3): 107–123, doi: 10.1016/S0012-365X(00)00264-8 , MR   1829840 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.