MycielskianIn the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number. Let the n vertices of the given graph G be v1, v2, . . . , vn.
Perfect graphIn graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices. The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families.
Line–line intersectionIn Euclidean geometry, the intersection of a line and a line can be the empty set, a point, or another line. Distinguishing these cases and finding the intersection have uses, for example, in computer graphics, motion planning, and collision detection. In three-dimensional Euclidean geometry, if two lines are not in the same plane, they have no point of intersection and are called skew lines.
PathwidthIn graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition.
Acyclic coloringIn graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number A(G) of a graph G is the fewest colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. A(G) ≤ 2 if and only if G is acyclic. Bounds on A(G) in terms of Δ(G), the maximum degree of G, include the following: A(G) ≤ 4 if Δ(G) = 3. A(G) ≤ 5 if Δ(G) = 4. A(G) ≤ 7 if Δ(G) = 5. A(G) ≤ 12 if Δ(G) = 6.
Cissoid of DioclesIn geometry, the cissoid of Diocles (; named for Diocles) is a cubic plane curve notable for the property that it can be used to construct two mean proportionals to a given ratio. In particular, it can be used to double a cube. It can be defined as the cissoid of a circle and a line tangent to it with respect to the point on the circle opposite to the point of tangency. In fact, the curve family of cissoids is named for this example and some authors refer to it simply as the cissoid.
Art gallery problemThe art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.
Archimedean spiralThe Archimedean spiral (also known as the arithmetic spiral) is a spiral named after the 3rd-century BC Greek mathematician Archimedes. It is the locus corresponding to the locations over time of a point moving away from a fixed point with a constant speed along a line that rotates with constant angular velocity. Equivalently, in polar coordinates (r, θ) it can be described by the equation with real numbers a and b.
Particular point topologyIn mathematics, the particular point topology (or included point topology) is a topology where a set is open if it contains a particular point of the topological space. Formally, let X be any non-empty set and p ∈ X. The collection of subsets of X is the particular point topology on X. There are a variety of cases that are individually named: If X has two points, the particular point topology on X is the Sierpiński space. If X is finite (with at least 3 points), the topology on X is called the finite particular point topology.
HyperbolaIn mathematics, a hyperbola (haɪˈpɜrbələ; pl. hyperbolas or hyperbolae -liː; adj. hyperbolic ˌhaɪpərˈbɒlɪk) is a type of smooth curve lying in a plane, defined by its geometric properties or by equations for which it is the solution set. A hyperbola has two pieces, called connected components or branches, that are mirror images of each other and resemble two infinite bows. The hyperbola is one of the three kinds of conic section, formed by the intersection of a plane and a double cone.
