Local rainbow colorings (Q433480): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
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 |
Revision as of 00:26, 30 June 2023
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