Name
Abstract | ||
|---|---|---|
Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A1, …, At of independent vertices. A set is called a dominating set of size |S| if for any vertex there is a w∈U such that (w, v)∈E(D). Let β(D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h = h(β(D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3-colored triangles. © 2011 Wiley Periodicals, Inc. J Graph Theory © 2012 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/jgt.20646 | Journal of Graph Theory |
Keywords | Field | DocType |
main result,edge colorings,largest independent set,wiley periodicals,inc. j graph theory,3-colored triangle,generalized gallai colorings,dominating set,multipartite digraph,classes a1,independent vertex,edge coloring,independent set | Graph theory,Discrete mathematics,Topology,Combinatorics,Dominating set,Multipartite,Vertex (geometry),Existential quantification,Cardinality,Independent set,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
71 | 3 | 0364-9024 |
Citations | PageRank | References |
3 | 0.50 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| András Gyárfás | 1 | 582 | 102.26 |
| Gábor Simonyi | 2 | 249 | 29.78 |
| Ágnes Tóth | 3 | 19 | 3.92 |