In graph theory, the Kneser graph K(n, k) (alternatively KGn,k) is the graph whose vertices correspond to the k-element subsets of a set of n elements...
14 KB (1,626 words) - 21:16, 14 August 2024
tropical curves. The Petersen graph is the complement of the line graph of K 5 {\displaystyle K_{5}} . It is also the Kneser graph K G 5 , 2 {\displaystyle...
24 KB (2,933 words) - 00:46, 29 August 2024
Odd chords are used to define strongly chordal graphs. 5. An odd graph is a special case of a Kneser graph, having one vertex for each (n − 1)-element subset...
108 KB (15,918 words) - 18:37, 5 October 2024
linear graphs. Certain Kneser graphs, and certain strongly regular graphs, are also locally linear. The question of how many edges locally linear graphs can...
24 KB (3,362 words) - 08:57, 2 January 2024
complete graph, as the tensor product Kn × K2, as the complement of the Cartesian direct product of Kn and K2, or as a bipartite Kneser graph Hn,1 representing...
11 KB (1,137 words) - 07:49, 6 March 2024
{\displaystyle J(n,2)} is the line graph of Kn and the complement of the Kneser graph K ( n , 2 ) . {\displaystyle K(n,2).} J ( n , k ) {\displaystyle J(n...
10 KB (1,283 words) - 21:27, 14 August 2024
complete graphs, refining the usual notion of colorings. Fractional and b-fold coloring can be defined using homomorphisms into Kneser graphs. T-colorings...
38 KB (4,860 words) - 02:17, 6 September 2024
subgraphs Shift graph, a family of triangle-free graphs with arbitrarily high chromatic number The Kneser graph K G 3 k − 1 , k {\displaystyle KG_{3k-1,k}}...
21 KB (2,524 words) - 00:41, 1 August 2024
The theorem may also be formulated in terms of graph theory: the independence number of the Kneser graph K G n , r {\displaystyle KG_{n,r}} for n ≥ 2 r...
44 KB (5,592 words) - 23:35, 28 July 2024
as the triangular graph, the Johnson graph J(n, 2), or the complement of the Kneser graph KGn,2. Triangular graphs are characterized by their spectra,...
43 KB (5,299 words) - 10:28, 5 July 2024