共查询到20条相似文献,搜索用时 531 毫秒
1.
We argue that there are 4 basic solution concepts for 2 × 2 symmetric games and corresponding to these, 4 basic human interactions and 4 types of societies. We propose a model in which the type of interaction is predicted by independence, inequality of power, communication, and mutuality of interests. We prove theorems classifying Moulin's inessential games in the case of an interior Nash equilibrium and argue that this explains coalition formation. We discuss classification of socially significant ideologies. 相似文献
2.
Jinfeng Feng Hans‐Erik Giesen Yubao Guo Gregory Gutin Tommy Jensen Arash Rafiey 《Journal of Graph Theory》2006,53(4):333-346
An edge‐colored graph H is properly colored if no two adjacent edges of H have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph G has a properly colored Hamilton path if and only if G has a spanning subgraph consisting of a properly colored path C0 and a (possibly empty) collection of properly colored cycles C1,C2,…, Cd such that provided . We prove this conjecture. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 333–346, 2006 相似文献
3.
In this paper, we introduce the almost inessential game (property) to the solution part of cooperative game theory, which generalizes the inessential game (property). Following the framework of Hamiache to characterize the Shapley value, we then define a new associated game to characterize the center-of-gravity of imputation set value (CIS-value) by means of the almost inessential game property, associated consistency, continuity and efficiency. It provides an interpretation to the CIS-value as the essentially unique fixed point of an endogenous transformation by self-evaluation of TU-games. In addition, symmetry and translation covariance are used to axiomatize the CIS-value instead of the almost inessential property. 相似文献
4.
《Journal of Graph Theory》2018,87(4):399-429
We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem. 相似文献
5.
6.
Solution of Vizing's Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
下载免费PDF全文
![点击此处可从《Journal of Graph Theory》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Let G be a Class 1 graph with maximum degree 4 and let be an integer. We show that any proper t‐edge coloring of G can be transformed to any proper 4‐edge coloring of G using only transformations on 2‐colored subgraphs (so‐called interchanges). This settles the smallest previously unsolved case of a well‐known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5‐edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7‐edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent. 相似文献
7.
L. Zádori 《Algebra Universalis》1995,33(2):216-236
We define nonextendible colored posets and zigzags of a poset. These notions are related to the earlier notions of gaps, holes, obstructions and zigzags considered by Duffus, Nevermann, Rival, Tardos and Wille. We establish some properties of zigzags. By using these properties we give a proof of the well known conjecture that states that any finite bounded poset which admits Jsson operations, also admits a near unanimity function. We also provide an infinite poset that shows that we cannot drop the finiteness in this conjecture.Presented by R. McKenzie. 相似文献
8.
A kernel by properly colored paths of an arc-colored digraph is a set of vertices of such that (i) no two vertices of are connected by a properly colored directed path in , and (ii) every vertex outside can reach by a properly colored directed path in . In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given. 相似文献
9.
For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyK
p
K are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticK
p
subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofK
n
. We use the Local Lemma to give a general upper bound forf. We determine for everyp the smallestq for whichf(n, p, q) is linear inn and the smallestq for whichf(n, p, q) is quadratic inn. We show that certain special cases of the problem closely relate to Turán type hypergraph problems introduced by Brown, Erds and T. Sós. Other cases lead to problems concerning proper edge colorings of complete graphs.Supported by OTKA grant 16414. 相似文献
10.
Benjamin Doerr 《Discrete Applied Mathematics》2006,154(4):650-659
We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well.We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2d/2 decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to (from n). The latter also speeds up the corresponding derandomization by a factor of . 相似文献
11.
12.
This work brings together ideas of mixing graph colorings, discrete homotopy, and precoloring extension. A particular focus is circular colorings. We prove that all the ‐colorings of a graph G can be obtained by successively recoloring a single vertex provided along the lines of Cereceda, van den Heuvel, and Johnson's result for k‐colorings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colorings coincide. As a corollary, we obtain an Albertson‐type extension theorem for ‐precolorings of circular cliques. Such a result was first conjectured by Albertson and West. General results on homomorphism mixing are presented, including a characterization of graphs G for which the endomorphism monoid can be generated through the mixing process. As in similar work of Brightwell and Winkler, the concept of dismantlability plays a key role. 相似文献
13.
14.
Consider the graph consisting of a triangle with a pendant edge. We describe the structure of rainbow ‐free edge colorings of a complete graph and provide some corresponding Gallai–Ramsey results. In particular, we extend a result of Gallai to find a partition of the vertices of a rainbow ‐free colored complete graph with a limited number of colors between the parts. We also extend some Gallai–Ramsey results of Chung and Graham, Faudree et al. and Gyárfás et al. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
15.
Multi-orientable group field theory (GFT) was introduced in Tanasa (J Phys A 45:165401, 2012), as a quantum field theoretical simplification of GFT, which retains a larger class of tensor graphs than the colored one. In this paper we define the associated multi-orientable identically independent distributed multi-orientable tensor model and we derive its 1/N expansion. In order to obtain this result, a partial classification of general tensor graphs is performed and the combinatorial notion of jacket is extended to the m.o. graphs. We prove that the leading sector is given, as in the case of colored models, by the so-called melon graphs. 相似文献
16.
In (strongly) perfect graphs, we define (strongly) canonical colorings; we show that for some classes of graphs, such colorings
can be obtained by sequential coloring techniques.
Chromatic properties ofP
4-free graphs based on such coloring techniques are mentioned and extensions to graphs containing no inducedP
5,
orC
5 are presented. In particular we characterize the class of graphs in which any maximal (or minimal) nodex in the vicinal preorder has the following property: there is either noP
4 havingx as a midpoint or noP
4 havingx as an endpoint. For such graphs, according to a result of Chvatal, there is a simple sequential coloring algorithm. 相似文献
17.
András Gyárfás Gábor N. Sárközy András Sebő Stanley Selkow 《Journal of Graph Theory》2010,64(3):233-243
A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐colorings of the edges of complete graphs. They actually turn out to be close to 2‐colorings—without being trivial extensions. Here, we give a method to extend some results on 2‐colorings to Gallai‐colorings, among them known and new, easy and difficult results. The method works for Gallai‐extendible families that include, for example, double stars and graphs of diameter at most d for 2?d, or complete bipartite graphs. It follows that every Gallai‐colored Kn contains a monochromatic double star with at least 3n+ 1/4 vertices, a monochromatic complete bipartite graph on at least n/2 vertices, monochromatic subgraphs of diameter two with at least 3n/4 vertices, etc. The generalizations are not automatic though, for instance, a Gallai‐colored complete graph does not necessarily contain a monochromatic star on n/2 vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization. We also investigate Ramsey numbers of graphs in Gallai‐colorings with a given number of colors. For any graph H let RG(r, H) be the minimum m such that in every Gallai‐coloring of Km with r colors, there is a monochromatic copy of H. We show that for fixed H, RG (r, H) is exponential in r if H is not bipartite; linear in r if H is bipartite but not a star; constant (does not depend on r) if H is a star (and we determine its value). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010 相似文献
18.
We study the perfect 2‐colorings (also known as the equitable partitions into two parts or the completely regular codes with covering radius 1) of the Johnson graphs . In particular, we classify all the realizable quotient matrices of perfect 2‐colorings for odd v. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 232–252, 2013 相似文献
19.
《Journal of Graph Theory》2018,87(2):135-148
Let ( be two positive integers. We generalize the well‐studied notions of ‐colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on n vertices, if the difference is smaller than 1, then there exists , such that the difference is at most . We also show that the notion of ‐colorings is equivalent to r‐colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26 , Springer Berlin Heidelberg, 2006, pp. 497–550)). 相似文献
20.
Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ‐coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper coloring by changing the color of one vertex. We show an analogue of Brooks' Theorem by proving that from any k‐coloring, , a Δ‐coloring of G can be obtained by a sequence of recolorings using only the original k colors unless
- – G is a complete graph or a cycle with an odd number of vertices, or
- – , G is Δ‐regular and, for each vertex v in G, no two neighbors of v are colored alike.