Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs (Q2142635): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3087759047 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 2009.08960 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 02:16, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs |
scientific article |
Statements
Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs (English)
0 references
27 May 2022
0 references
For a graph \(G\) and a family \(\mathcal{H}\) of subgraphs of \(G\), we say a (not necessarily proper) colouring of the edges of \(G\) is \(\mathcal{H}\)-polychromatic if every graph in \(\mathcal{H}\) has edges of every colour used in the colouring of \(G\). The largest possible number of colourings in an \(\mathcal{H}\)-polychromatic colouring of \(G\) is called the \(\mathcal{H}\)-polychromatic number of \(G\) and is denoted by poly\(_{\mathcal{H}}(G)\). We consider the case where \(G\) is a complete graph on \(n\) vertices and abuse notation by writing poly\(_{\mathcal H}(n)\) for poly\(_{\mathcal H}(K_{n})\). As by Ramsey's theorem, if the graphs in \(\mathcal{H}\) were of bounded size we would get poly\(_{\mathcal H}(n)\)=1, we should only look at cases where the graphs in \(\mathcal{H}\) increase in size with \(n\). In [\textit{M. Axenovich} et al., J. Graph Theory 87, No. 4, 660--671 (2018; Zbl 1386.05051)] the value of poly\(_{\mathcal{H}}(n)\) is determined when \(\mathcal{H}\) is the set of perfect matchings (\(n\) even) and is approximated to within a small additive constant when \(\mathcal{H}\) is the set of 2-regular graphs or \(\mathcal{H}\) is the set of Hamilton cycles. The paper under review deals with the cases where (for a fixed integer \(q\)) \(\mathcal{H}\) is the set of all matchings covering \(n-q\) vertices, all \((n-q)\) cycles and all 2-regular graphs on at least \(n-q\) vertices. In all cases the exact answer is obtained. Note that for \(q=0\) the results confirm and extend those of Axenovich et al. The optimal colourings are based on certain orderings. There are links with extensions of results on Ramsey numbers for cycles in a graph. A conjecture more general than most of the results in the paper is also made.
0 references
polychromatic colouring
0 references
matching
0 references
long cycle
0 references