Local rainbow colorings (Q433480): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / review text | |||
From the authors' abstract: ``Given a graph \(H\), we denote by \(C(n,H)\) the minimum number \(k\) such that the following holds. There are \(n\) colorings of \(E(K_n)\) with \(k\) colors, each associated with one of the vertices of \(K_n\), such that for every copy \(T\) of \(H\) in \(K_n\) at least one of the colorings that are associated with \(V(T)\) assigns distinct colors to all the edges of \(E(T)\). We characterize the set of all graphs \(H\) for which \(C(n,H)\) is bounded by some absolute constant \(c(H)\), prove a general upper bound, and obtain lower and upper bounds for several graphs of special interest. A special case of our results partially answers an extremal question of Karchmer and Wigderson motivated by the investigation of the computational power of span programs.'' | |||
Property / review text: From the authors' abstract: ``Given a graph \(H\), we denote by \(C(n,H)\) the minimum number \(k\) such that the following holds. There are \(n\) colorings of \(E(K_n)\) with \(k\) colors, each associated with one of the vertices of \(K_n\), such that for every copy \(T\) of \(H\) in \(K_n\) at least one of the colorings that are associated with \(V(T)\) assigns distinct colors to all the edges of \(E(T)\). We characterize the set of all graphs \(H\) for which \(C(n,H)\) is bounded by some absolute constant \(c(H)\), prove a general upper bound, and obtain lower and upper bounds for several graphs of special interest. A special case of our results partially answers an extremal question of Karchmer and Wigderson motivated by the investigation of the computational power of span programs.'' / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Dan S. Archdeacon / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C35 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6056109 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
edge-colorings | |||
Property / zbMATH Keywords: edge-colorings / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
rainbow colorings | |||
Property / zbMATH Keywords: rainbow colorings / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.4310/joc.2011.v2.n2.a6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2328006356 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:42, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Local rainbow colorings |
scientific article |
Statements
Local rainbow colorings (English)
0 references
16 July 2012
0 references
From the authors' abstract: ``Given a graph \(H\), we denote by \(C(n,H)\) the minimum number \(k\) such that the following holds. There are \(n\) colorings of \(E(K_n)\) with \(k\) colors, each associated with one of the vertices of \(K_n\), such that for every copy \(T\) of \(H\) in \(K_n\) at least one of the colorings that are associated with \(V(T)\) assigns distinct colors to all the edges of \(E(T)\). We characterize the set of all graphs \(H\) for which \(C(n,H)\) is bounded by some absolute constant \(c(H)\), prove a general upper bound, and obtain lower and upper bounds for several graphs of special interest. A special case of our results partially answers an extremal question of Karchmer and Wigderson motivated by the investigation of the computational power of span programs.''
0 references
edge-colorings
0 references
rainbow colorings
0 references