Editing Glossary of graph theory (section)

==C==
{{glossary}}

{{term|C|''C''}}
{{defn|{{math|''C''<sub>''n''</sub>}} is an {{mvar|n}}-vertex [[cycle graph]]; see {{gli|cycle}}.}}

{{term|cactus}}
{{defn|A [[cactus graph]], cactus tree, cactus, or Husimi tree is a connected graph in which each edge belongs to at most one cycle. Its blocks are cycles or single edges. If, in addition, each vertex belongs to at most two blocks, then it is called a Christmas cactus.}}

{{term|cage}}
{{defn|A [[Cage (graph theory)|cage]] is a regular graph with the smallest possible order for its girth.}}

{{term|canonical}}
{{term|canonization|multi=y}}
{{defn|A [[canonical form]] of a graph is an invariant such that two graphs have equal invariants if and only if they are isomorphic. Canonical forms may also be called canonical invariants or complete invariants, and are sometimes defined only for the graphs within a particular family of graphs. [[Graph canonization]] is the process of computing a canonical form.}}

{{term|card}}
{{defn|A graph formed from a given graph by deleting one vertex, especially in the context of the [[reconstruction conjecture]]. See also {{gli|deck}}, the multiset of all cards of a graph.}}

{{term|carving width}}
{{defn|Carving width is a notion of graph width analogous to branchwidth, but using hierarchical clusterings of vertices instead of hierarchical clusterings of edges.}}

{{term|caterpillar}}
{{defn|A [[caterpillar tree]] or caterpillar is a tree in which the internal nodes induce a path.}}

{{term|center}}
{{defn|The [[Graph center|center]] of a graph is the set of vertices of minimum {{gli|eccentricity}}.}}

{{term|centroid}}
{{defn|A [[Centroid (graph theory)|centroid]] of a tree is a vertex {{mvar|v}} such that if rooted at {{mvar|v}}, no other vertex has subtree size greater than half the size of the tree.}}

{{term|chain}}
{{defn|no=1|Synonym for {{gli|walk}}.}}
{{defn|no=2|When applying methods from [[algebraic topology]] to graphs, an element of a [[chain complex]], namely a set of vertices or a set of edges.}}

{{term|Cheeger constant}}
{{defn|See {{gli|expansion}}.}}

{{term|cherry}}
{{defn|A cherry is a path on three vertices.<ref>{{citation|last1=Sudakov|first1=Benny|last2=Volec|first2=Jan|title=Properly colored and rainbow copies of graphs with few cherries|journal=Journal of Combinatorial Theory, Series B|volume=122|issue=1|year=2017|pages=391–416|doi=10.1016/j.jctb.2016.07.001|doi-access=free|arxiv=1504.06176}}.</ref>}}

{{term|chi|''&chi;''}}
{{defn|{{math|''&chi;''(''G'')}} (using the Greek letter chi) is the chromatic number of {{mvar|G}} and {{math|''&chi;''{{hsp}}′(''G'')}} is its chromatic index; see {{gli|chromatic}} and {{gli|coloring}}.}}

{{term|child}}
{{defn|In a rooted tree, a child of a vertex {{mvar|v}} is a neighbor of {{mvar|v}} along an outgoing edge, one that is directed away from the root.}}

{{term|chord}}
{{term|chordal|multi=y}}
{{defn|no=1|A chord of a cycle is an edge that does not belong to the cycle, for which both endpoints belong to the cycle.}}
{{defn|no=2|A [[chordal graph]] is a graph in which every cycle of four or more vertices has a chord, so the only induced cycles are triangles.}}
{{defn|no=3|A [[strongly chordal graph]] is a chordal graph in which every cycle of length six or more has an odd chord.}}
{{defn|no=4|A [[chordal bipartite graph]] is not chordal (unless it is a forest); it is a bipartite graph in which every cycle of six or more vertices has a chord, so the only induced cycles are 4-cycles.}}
{{defn|no=5|A [[Chord (geometry)|chord of a circle]] is a line segment connecting two points on the circle; the [[intersection graph]] of a collection of chords is called a [[circle graph]].}}

{{term|chromatic}}
{{defn|Having to do with coloring; see {{gli|color}}. Chromatic graph theory is the theory of graph coloring. The [[chromatic number]] {{math|''&chi;''(''G'')}} is the minimum number of colors needed in a proper coloring of {{mvar|G}}. {{math|''&chi;''{{hsp}}′(''G'')}} is the [[chromatic index]] of {{mvar|G}}, the minimum number of colors needed in a proper [[edge coloring]] of {{mvar|G}}.}}

{{term|choosable}}
{{term|choosability|multi=y}}
{{defn|A graph is {{mvar|k}}-choosable if it has a [[list coloring]] whenever each vertex has a list of {{mvar|k}} available colors. The choosability of the graph is the smallest {{mvar|k}} for which it is {{mvar|k}}-choosable.}}

{{term|circle}}
{{defn|A [[circle graph]] is the [[intersection graph]] of chords of a circle.}}

{{term|circuit}}
{{defn|A circuit may refer to a closed trail or an element of the [[cycle space]] (an Eulerian spanning subgraph). The [[circuit rank]] of a graph is the dimension of its cycle space.}}

{{term|circumference}}
{{defn|The [[Circumference (graph theory)|circumference]] of a graph is the length of its longest simple cycle. The graph is Hamiltonian if and only if its circumference equals its order.}}

{{term|class}}
{{defn|no=1|A [[Class (set theory)|class]] of graphs or family of graphs is a (usually infinite) collection of graphs, often defined as the graphs having some specific property. The word "class" is used rather than "set" because, unless special restrictions are made (such as restricting the vertices to be drawn from a particular set, and defining edges to be sets of two vertices) classes of graphs are usually not sets when formalized using set theory.}}
{{defn|no=2|A color class of a colored graph is the set of vertices or edges having one particular color.}}
{{defn|no=3|In the context of [[Vizing's theorem]], on edge coloring simple graphs, a graph is said to be of class one if its chromatic index equals its maximum degree, and class two if its chromatic index equals one plus the degree. According to Vizing's theorem, all simple graphs are either of class one or class two.}}

{{term|claw}}
{{defn|A [[Claw (graph theory)|claw]] is a tree with one internal vertex and three leaves, or equivalently the complete bipartite graph {{math|''K''<sub>1,3</sub>}}. A [[claw-free graph]] is a graph that does not have an induced subgraph that is a claw.}}

{{term|clique}}
{{defn|A [[Clique (graph theory)|clique]] is a set of mutually adjacent vertices (or the complete subgraph induced by that set).  Sometimes a clique is defined as a maximal set of mutually adjacent vertices (or maximal complete subgraph), one that is not part of any larger such set (or subgraph). A {{mvar|k}}-clique is a clique of order {{mvar|k}}. The [[clique number]] {{math|''&omega;''(''G'')}} of a graph {{mvar|G}} is the order of its largest clique. The [[clique graph]] of a graph ''G'' is the [[intersection graph]] of the maximal cliques in ''G''. See also {{gli|biclique}}, a complete bipartite subgraph.}}

{{term|clique tree}}
{{defn|A synonym for a {{gli|block graph}}.}}

{{term|clique-width}}
{{defn|The [[clique-width]] of a graph {{mvar|G}} is the minimum number of distinct labels needed to construct {{mvar|G}} by operations that create a labeled vertex, form the disjoint union of two labeled graphs, add an edge connecting all pairs of vertices with given labels, or relabel all vertices with a given label. The graphs of clique-width at most {{math|2}} are exactly the [[cograph]]s.}}

{{term|closed}}
{{defn|no=1|A closed neighborhood is one that includes its central vertex; see {{gli|neighbourhood}}.}}
{{defn|no=2|A closed walk is one that starts and ends at the same vertex; see {{gli|walk}}.}}
{{defn|no=3|A graph is transitively closed if it equals its own transitive closure; see {{gli|transitive}}.}}
{{defn|no=4|A graph property is closed under some operation on graphs if, whenever the argument or arguments to the operation have the property, then so does the result. For instance, hereditary properties are closed under induced subgraphs; monotone properties are closed under subgraphs; and minor-closed properties are closed under minors.}}

{{term|closure}}
{{defn|no=1|For the transitive closure of a directed graph, see {{gli|transitive}}.}}
{{defn|no=2|A closure of a directed graph is a set of vertices that have no outgoing edges to vertices outside the closure. For instance, a sink is a one-vertex closure. The [[closure problem]] is the problem of finding a closure of minimum or maximum weight.}}

{{term|co-}}
{{defn|This prefix has various meanings usually involving [[complement graph]]s. For instance, a [[cograph]] is a graph produced by operations that include complementation; a [[cocoloring]] is a coloring in which each vertex induces either an independent set (as in proper coloring) or a clique (as in a coloring of the complement).}}

{{term|color}}
{{term|coloring|multi=y}}
{{defn|no=1|A [[graph coloring]] is a labeling of the vertices of a graph by elements from a given set of colors, or equivalently a partition of the vertices into subsets, called "color classes", each of which is associated with one of the colors.}}
{{defn|no=2|Some authors use "coloring", without qualification, to mean a proper coloring, one that assigns different colors to the endpoints of each edge. In graph coloring, the goal is to find a proper coloring that uses as few colors as possible; for instance, [[bipartite graph]]s are the graphs that have colorings with only two colors, and the [[four color theorem]] states that every [[planar graph]] can be colored with at most four colors. A graph is said to be {{mvar|k}}-colored if it has been (properly) colored with {{mvar|k}} colors, and {{mvar|k}}-colorable or {{mvar|k}}-chromatic if this is possible.}}
{{defn|no=3|Many variations of coloring have been studied, including [[edge coloring]] (coloring edges so that no two edges with the same endpoint share a color), [[list coloring]] (proper coloring with each vertex restricted to a subset of the available colors), [[acyclic coloring]] (every 2-colored subgraph is acyclic), co-coloring (every color class induces an independent set or a clique), [[complete coloring]] (every two color classes share an edge), and [[total coloring]] (both edges and vertices are colored).}}
{{defn|no=4|The coloring number of a graph is one plus the [[Degeneracy (graph theory)|degeneracy]]. It is so called because applying a greedy coloring algorithm to a degeneracy ordering of the graph uses at most this many colors.}}

{{term|comparability}}
{{defn|An undirected graph is a [[comparability graph]] if its vertices are the elements of a [[partially ordered set]] and two vertices are adjacent when they are comparable in the partial order. Equivalently, a comparability graph is a graph that has a transitive orientation. Many other classes of graphs can be defined as the comparability graphs of special types of partial order.}}

{{term|complement}}
{{defn|The [[complement graph]] <math>\bar{G}</math> of a simple graph {{mvar|G}} is another graph on the same vertex set as {{mvar|G}}, with an edge for each two vertices that are not adjacent in {{mvar|G}}.}}

{{term|complete}}
{{defn|no=1|A [[complete graph]] is one in which every two vertices are adjacent: all edges that could exist are present. A complete graph with {{mvar|n}} vertices is often denoted {{math|''K''<sub>''n''</sub>}}. A [[complete bipartite graph]] is one in which every two vertices on opposite sides of the partition of vertices are adjacent. A complete bipartite graph with {{mvar|a}} vertices on one side of the partition and {{mvar|b}} vertices on the other side is often denoted {{math|''K''<sub>''a'',''b''</sub>}}. The same terminology and notation has also been extended to [[complete multipartite graph]]s, graphs in which the vertices are divided into more than two subsets and every pair of vertices in different subsets are adjacent; if the numbers of vertices in the subsets are {{math|''a'', ''b'', ''c'', ...}} then this graph is denoted {{math|''K''<sub>''a'', ''b'', ''c'', ...</sub>}}.}}
{{defn|no=2|A completion of a given graph is a supergraph that has some desired property. For instance, a [[chordal completion]] is a supergraph that is a chordal graph.}}
{{defn|no=3|A complete matching is a synonym for a [[perfect matching]]; see {{gli|matching}}.}}
{{defn|no=4|A [[complete coloring]] is a proper coloring in which each pairs of colors is used for the endpoints of at least one edge. Every coloring with a minimum number of colors is complete, but there may exist complete colorings with larger numbers of colors. The [[achromatic number]] of a graph is the maximum number of colors in a complete coloring.}}
{{defn|no=5|A complete invariant of a graph is a synonym for a canonical form, an invariant that has different values for non-isomorphic graphs.}}

{{term|component}}
{{defn|A [[Connected component (graph theory)|connected component]] of a graph is a maximal connected subgraph. The term is also used for maximal subgraphs or subsets of a graph's vertices that have some higher order of connectivity, including [[biconnected component]]s, [[triconnected component]]s, and [[strongly connected component]]s.}}

{{term|condensation}}
{{defn|The [[Condensation (graph theory)|condensation]] of a directed graph {{mvar|G}} is a directed acyclic graph with one vertex for each strongly connected component of {{mvar|G}}, and an edge connecting pairs of components that contain the two endpoints of at least one edge in {{mvar|G}}.}}

{{term|cone}}
{{defn|A graph that contains a [[universal vertex]].}}

{{term|connect}}
{{defn|Cause to be {{gli|connected}}.}}

{{term|connected}}
{{defn|A [[Connectivity (graph theory)|connected graph]] is one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions), [[k-vertex-connected graph|{{mvar|k}}-vertex-connected graphs]] (removing fewer than {{mvar|k}} vertices cannot disconnect the graph), and [[k-edge-connected graph|{{mvar|k}}-edge-connected graphs]] (removing fewer than {{mvar|k}} edges cannot disconnect the graph).}}

{{term|connected component}}
{{defn|Synonym for {{gli|component}}.}}

{{term|contraction}}
{{defn|[[Edge contraction]] is an elementary operation that removes an edge from a graph while merging the two vertices that it previously joined. Vertex contraction (sometimes called vertex identification) is similar, but the two vertices are not necessarily connected by an edge. Path contraction occurs upon the set of edges in a path that contract to form a single edge between the endpoints of the path. The inverse of edge contraction is vertex splitting.}}

{{term|converse}}
{{defn|The converse graph is a synonym for the transpose graph; see {{gli|transpose}}.}}

{{term|core}}
{{defn|no=1|A [[k-core|{{mvar|k}}-core]] is the induced subgraph formed by removing all vertices of degree less than {{mvar|k}}, and all vertices whose degree becomes less than {{mvar|k}} after earlier removals. See {{gli|degeneracy}}.}}
{{defn|no=2|A [[Core (graph theory)|core]] is a graph {{mvar|G}} such that every [[graph homomorphism]] from {{mvar|G}} to itself is an isomorphism.}}
{{defn|no=3|The [[Core (graph theory)|core]] of a graph {{mvar|G}} is a minimal graph {{mvar|H}} such that there exist homomorphisms from {{mvar|G}} to {{mvar|H}} and vice versa. {{mvar|H}} is unique up to isomorphism. It can be represented as an induced subgraph of {{mvar|G}}, and is a core in the sense that all of its self-homomorphisms are isomorphisms.}}
{{defn|no=4|In the theory of graph matchings, the core of a graph is an aspect of its [[Dulmage–Mendelsohn decomposition]], formed as the union of all maximum matchings.}}

{{term|cotree}}
{{defn|no=1|The complement of a [[spanning tree]].}}
{{defn|no=2|A rooted tree structure used to describe a [[cograph]], in which each cograph vertex is a leaf of the tree, each internal node of the tree is labeled with 0 or 1, and two cograph vertices are adjacent if and only if their lowest common ancestor in the tree is labeled 1.}}

{{term|cover}}
{{defn|A [[vertex cover]] is a set of vertices incident to every edge in a graph. An [[edge cover]] is a set of edges incident to every vertex in a graph. A set of subgraphs of a graph covers that graph if its [[Graph operations#Binary operations|union]] – taken vertex-wise and edge-wise – is equal to the graph.}}

{{term|critical}}
{{defn|A critical graph for a given property is a graph that has the property but such that every subgraph formed by deleting a single vertex does not have the property. For instance, a [[factor-critical graph]] is one that has a perfect matching (a 1-factor) for every vertex deletion, but (because it has an odd number of vertices) has no perfect matching itself. Compare ''hypo-'', used for graphs which do not have a property but for which every one-vertex deletion does.}}

{{term|cube}}
{{term|cubic|multi=y}}
{{defn|no=1|[[Cube graph]], the eight-vertex graph of the vertices and edges of a cube.}}
{{defn|no=2|[[Hypercube graph]], a higher-dimensional generalization of the cube graph.}}
{{defn|no=3|[[Folded cube graph]], formed from a hypercube by adding a matching connecting opposite vertices.}}
{{defn|no=4|[[Halved cube graph]], the [[half-square]] of a hypercube graph.}}
{{defn|no=5|[[Partial cube]], a distance-preserving subgraph of a hypercube.}}
{{defn|no=6|The cube of a graph {{mvar|G}} is the [[graph power]] {{math|''G''<sup>3</sup>}}.}}
{{defn|no=7|[[Cubic graph]], another name for a {{math|3}}-regular graph, one in which each vertex has three incident edges.}}
{{defn|no=8|[[Cube-connected cycles]], a cubic graph formed by replacing each vertex of a hypercube by a cycle.}}

{{term|cut}}
{{term|cut-set|multi=y}}
{{defn|A [[cut (graph theory)|cut]] is a partition of the vertices of a graph into two subsets, or the set (also known as a cut-set) of edges that span such a partition, if that set is non-empty. An edge is said to span the partition if it has endpoints in both subsets. Thus, the removal of a cut-set from a connected graph disconnects it.}}

{{term|cut point}}
{{defn|See {{gli|articulation point}}.}}

{{term|cut space}}
{{defn|The [[cut space]] of a graph is a [[GF(2)]]-[[vector space]] having the {{gli|cut-set}}s of the graph as its elements and [[symmetric difference]] of sets as its vector addition operation.}}

{{term|cycle}}
{{defn|no=1|A [[Cycle (graph theory)|cycle]] may be either a kind of graph or a kind of {{gli|walk}}.  As a walk it may be either be a closed walk (also called a {{gli|tour}}) or more usually a closed walk without repeated vertices and consequently edges (also called a simple cycle). In the latter case it is usually regarded as a graph, i.e., the choices of first vertex and direction are usually considered unimportant; that is, [[cyclic permutation]]s and reversals of the walk produce the same cycle. Important special types of cycle include [[Hamiltonian cycle]]s, [[induced cycle]]s, [[peripheral cycle]]s, and the shortest cycle, which defines the [[Girth (graph theory)|girth]] of a graph. A {{mvar|k}}-cycle is a cycle of length {{mvar|k}}; for instance a {{mvar|2}}-cycle is a [[digon]] and a {{math|3}}-cycle is a triangle. A [[cycle graph]] is a graph that is itself a simple cycle; a cycle graph with {{mvar|n}} vertices is commonly denoted {{math|''C''<sub>''n''</sub>}}. }}
{{defn|no=2|The [[cycle space]] is a [[vector space]] generated by the simple cycles in a graph, often over the field of 2 elements but also over other fields.}}

{{glossary end}}