Premium
Gallai colorings and domination in multipartite digraphs
Author(s) -
Gyárfás András,
Simonyi Gábor,
Tóth Ágnes
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20646
Subject(s) - combinatorics , multipartite , mathematics , digraph , vertex (graph theory) , dominating set , independent set , graph , cardinality (data modeling) , discrete mathematics , computer science , physics , quantum mechanics , quantum entanglement , quantum , data mining
Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A 1 , …, A t 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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom