A finite basis characterization of alpha-split colorings (Q1850023): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: András Gyárfás / rank | |||
Property / author | |||
Property / author: Jenő Lehel / rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Revision as of 19:10, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A finite basis characterization of alpha-split colorings |
scientific article |
Statements
A finite basis characterization of alpha-split colorings (English)
0 references
2 December 2002
0 references
A graph is called split if there exists a partition of its vertices into two sets so that one set induces a clique and the second set induces an independent set. This concept can be generalized as follows: Fix \(t>1\), a positive integer, and \({\mathbf a}=(a_1,\dots,a_t)\) a vector of nonnegative integers. A \(t\)-colouring of the edges of a complete graph is called \({\mathbf a}\)-split if there exists a partition of the vertices into \(t\) sets \(V_1,\dots,V_t\) such that every set of \(a_i+1\) vertices in \(V_i\) contains an edge of colour \(i\), for \(i=1,2,\dots,t\). It is shown that for any given \({\mathbf a}\), the family of \({\mathbf a}\)-split colourings is characterized by a finite set of forbidden induced subcolourings. The result is obtained by the combination of a theorem of \textit{M. Deza} [J. Comb. Theory, Ser. B 16, 166-167 (1974; Zbl 0263.05007)] and Ramsey's theorem. An analogous hypergraph version is obtained as well. The authors also treat some variations of the problem. The paper extends works of \textit{A. E. Kézdy} et al. [J. Comb. Theory, Ser. A 73, 353-359 (1996; Zbl 0844.05003)] and \textit{A. Gyárfás} [J. Comb. Theory, Ser. A 81, 255-261 (1998; Zbl 0893.05012)].
0 references
generalized colouring
0 references
Ramsey number
0 references
finite basis
0 references
clique
0 references
independent set
0 references