Search
Search results for: infinite game chromatic number
-
Infinite chromatic games
PublicationIn the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...
-
Total chromatic sum for trees
PublicationThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
-
2-Coloring number revisited
Publication2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
Liczby Ramseya on-line dla różnych klas grafów
PublicationRozpatrujemy grę rozgrywaną na nieskończonej liczbie wierzchołków, w której każda runda polega na wskazaniu krawędzi przez jednego gracza - Budowniczego oraz pokolorowaniu jej przez drugiego gracza - Malarkę na jeden z dwóch kolorów, czerwony lub niebieski. Celem Budowniczego jest zmuszenie Malarki do stworzenia monochromatycznej kopii wcześniej ustalonego grafu H w jak najmniejszej możliwej liczbie ruchów. Zakładamy, że gracze...
-
On-line Ramsey Numbers of Paths and Cycles
PublicationConsider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the \emph{on-line Ramsey number} $\tilde{r}(G,H)$. In...
-
T-colorings, divisibility and circular chromatic number
PublicationLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
Equitable colorings of some variation of corona products of cubic graphs
PublicationThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
ANFIS-Based NPC Population Control in Video Games
PublicationModern computer games aim at providing rich, vivid worlds. The aim is to encourage the player to explore and interact with the in-game world. To describe the complex relations between in-game NPCs and their surrounding fuzzy logic is used. The paper presents ANFIS based population control in the video game. We present an approach allowing stabilizing the number of NPCs in-game by providing a certain amount of food to the environment....
-
Equitable coloring of corona multiproducts of graphs
PublicationWe give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.
-
Product Graph Invariants with Applications in the Theory of Information
PublicationThere are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled...
-
The Backbone Coloring Problem for Small Graphs
PublicationIn this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...
-
Minimum order of graphs with given coloring parameters
PublicationA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
Indirect control over subordinate units
PublicationDeveloping a game universe usually involves creation of various units which can be both, encountered by a player or controlled by him. There is a number of works considering autonomous behaviours of units wandering around the game world. When it comes to the units controlled by the player, they often are lack of autonomy and are strictly controlled by the player. This paper presents a concept of units behaviour depending on their...
-
INDIRECT CONTROL OVER SUBORDINATE UNITS
PublicationDeveloping a game universe usually involves creation of various units which can be both, encountered by a player or controlled by him. There is a number of works considering autonomous behaviors of units wandering around the game world. When it comes to the units controlled by the player, they are often deprived of autonomy and are strictly controlled by the player. This paper presents a concept of units behavior depending on their...
-
Integration of brood units in game universe
PublicationAn access to a great number of various services allows for decomposition of complex problems Developing a game universe usually involves creation of various units which can be encountered by a player. Those can be lonely or organized in broods animals and monsters wandering around the game world. In order to provide natural gaming experience those units should behave variously depending on the world situation. Those behaviours...
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Linear game non-contextuality and Bell inequalities—a graph-theoretic approach
PublicationWe study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...
-
Equitable coloring of corona products of graphs
PublicationIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
-
Anna Zielińska dr
PeopleIn 2016, she started her work at the Faculty of Management and Economics of the Gdańsk University of Technology. Since 2018, a member of the board of the International Project Management Association Young Crew Polska. Author of numerous scientific publications in the field of crisis management, project and health program management, and improvement of business entities. Scientific and research interests include program and project...
-
Optimal backbone coloring of split graphs with matching backbones
PublicationFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Application of Game Theory to Conflict Management in a Construction Contract
PublicationInterest has recently grown in the application of game theory (GT) to solve a number of diverse problems in the field of construction. The use of GT by a general contractor (GC) of construction works to indicate the best strategy leading to winning court proceedings in a situation of conflict with investor (IN), has not been investigated until now. Thus the aim of this paper is to indicate the optimal strategy from the GC viewpoint...
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
Restricted open shop scheduling
PublicationIn the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule)....
-
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
-
Variational Method of Finding Streamlines in Ring Cascades for Creeping Flows
PublicationThis paper presents a new, analytical method of finding streamlinesfor creeping flows inside a ring cascade which is composed of an infinite number of infinitely thin blades. An analytical solution has been obtained through minimisation of a dissipation functional by means of variational calculus method. The necessary condition for optimum of a functional gives the Stokes equation if some additional assumptions are introduced....
-
Solvation of alkaline earth metal ions in N,N-dimethylformamide and N,N-dimethylacetamide – A volumetric and acoustic study
PublicationDensities and sound velocities at temperatures (298.15, 303.15, 308.15, 313.15 and 318.15) K of magnesium(II), calcium(II) and strontium(II) rifluoromethanesulfonates (triflates), as well as barium(II) perchloratein N,N-dimethylformamide (dmf) and N,N-dimethylacetamide (dma) have been measured over the composition range studied. From these results, apparent molar volumes and apparent molar isentropic compressibilities at infinite...
-
Trees having many minimal dominating sets
PublicationWe provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...
-
Graph classes generated by Mycielskians
PublicationIn this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
-
Characteristic of Morpholinium Ionic Liquids as Gas Chromatography Stationary Phases with McReynolds Constants and Activity Coefficients at Infinite Dilution
PublicationIn this work, four ionic liquids based on N-alkyl-N-methylmorpholinium cation ([Mor1,R] where R= 2, 4, 8, 10) and bis(trifluoromethanesulfonyl)imide anion [TFSI] were synthesized. Using gas-liquid chromatography a number of parameters describing the sorption properties of the investigated ionic liquids were determined. The values of Kovats indices, McReynolds constants, and activity coefficients at infinite dilution were the basis...
-
Possible uses of crisis situation aiding system in virtual world simulation
PublicationMany of the real world crisis situations like spreading fire, hostile units attack, flood, and etc. are commonly used in computer games where a simulation of extensive virtual world is crucial. This paper presents some ideas for possible uses of existing crisis situation aiding system in such environments. Moreover, it shows how this kind of system can be taught during subsequent games with a large number of players. As an example...
-
On the lower smoothing bound in identification of time-varying systems
PublicationIn certain applications of nonstationary system identification the model-based decisions can be postponed, i.e. executed with a delay. This allows one to incorporate in the identification process not only the currently available information, but also a number of ''future'' data points. The resulting estimation schemes, which involve smoothing, are not causal. Assuming that the infinite observation history is available, the paper...
-
A construction for the hat problem on a directed graph
PublicationA team of n players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The...
-
A NOTE ON ON-LINE RAMSEY NUMBERS FOR QUADRILATERALS
PublicationWe consider on-line Ramsey numbers defined by a game played between two players, Builder and Painter. In each round Builder draws an the edge and Painter colors it either red or blue, as it appears. Builder’s goal is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number \widetilde{r}(H) of...
-
Necessary and Sufficient Condition for State-Independent Contextual Measurement Scenarios
PublicationThe problem of identifying measurement scenarios capable of revealing state-independent contextuality in a given Hilbert space dimension is considered. We begin by showing that for any given dimension d and any measurement scenario consisting of projective measurements, (i) the measure of contextuality of a quantum state is entirely determined by its spectrum, so that pure and maximally mixed states represent the two extremes...
-
Multiple access in ad-hoc wireless LANs with noncooperative stations
PublicationA class of contention-type MAC protocols (e.g., CSMA/CA) relies on random deferment of packet transmission, and subsumes a deferment selection strategy and a scheduling policy that determines the winner of each contention cycle. This paper examines contention-type protocols in a noncooperative an ad-hoc wireless LAN setting, where a number of stations self-optimise their strategies to obtain a more-than-fair bandwidth share. Two...
-
The complete list of two-dimensional number-conserving ternary cellular automata
Open Research DataThis dataset contains a complete list of all 1327 two-dimensional number-conserving cellular automata with the state set {0,1,2} (the so-called ternary cellular automata) based on adjacent cells only, i.e. with the von Neumann neighborhood. The detailed definitions and the method of enumerating are given in the paper:
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
Bringing Common Sense to WordNet with a Word Game
PublicationWe present a tool for common sense knowledge acquisition in form of a twenty questions game. The described approach uses WordNet dictionary, which rich taxonomy allows to keep cognitive economy and accelerate knowledge propagation, although sometimes inferences made on hierarchical relations result in noise. We extend the dictionary with common sense assertions acquired during the games played with humans. The facts added to the...
-
Towards a classification of networks with asymmetric inputs
PublicationCoupled cell systems associated with a coupled cell network are determined by (smooth) vector fields that are consistent with the network structure. Here, we follow the formalisms of Stewart et al (2003 SIAM J. Appl. Dyn. Syst. 2, 609–646), Golubitsky et al (2005 SIAM J. Appl. Dyn. Syst. 4, 78–100) and Field (2004 Dyn. Syst. 19, 217–243). It is known that two non-isomorphic n-cell coupled networks can determine the same sets of...
-
Effect of temperature and ionic strength on volumetric and acoustic properties of solutions of urea alkil derivatives in aqueous NaCl
PublicationThe present work was undertaken to study volumetric and acoustic properties for diluted solutions of tetramethylurea in pure water and for urea, n-propylurea, n-butylurea and tetramethylurea in 0.5 or 1 moldm3 aqueous solutions of sodium chloride. This paper presents measured values of densities and sound velocities at T = (288.15, 298.15 and 308.15) K. From these data the apparent molar volumes, , adiabatic compressibilities,...
-
Limitations of Emotion Recognition in Software User Experience Evaluation Context
PublicationThis paper concerns how an affective-behavioural- cognitive approach applies to the evaluation of the software user experience. Although it may seem that affect recognition solutions are accurate in determining the user experience, there are several challenges in practice. This paper aims to explore the limitations of the automatic affect recognition applied in the usability context as well as...
-
Dynamic coloring of graphs
PublicationDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
-
Application of the discrete Green's function-based antenna simulations for excitation of the total-field/scattered-field interface in the FDTD method
PublicationIn this article, the discrete Green's function formulation of the finite-difference time-domain (DGF-FDTD) method is proposed for simulation of wire antennas irradiating inhomogeneous dielectric scatterers. Surface equivalence theorem in the discrete domain is used to separate the problem into an inhomogeneous domain and a wire antenna that are simulated with the use of FDTD and DGF-FDTD, respectively. Then, the excitation of the...
-
Application Isssues of the Semi-Markov Reliability Model
PublicationPredicting the reliability of marine internal combustion engines, for instance, is of particular importance, as it makes it possible to predict their future reliability states based on the information on the past states. Correct reliability prediction is a complex process which consists in processing empirical results obtained from operating practice, complemented by analytical considerations. The process of technical state changes...
-
Hybrid Technique Combining the FDTD Method and Its Convolution Formulation Based on the Discrete Green's Function
PublicationIn this letter, a technique combining the finite-difference time-domain (FDTD) method and its formulation based on the discrete Green's function (DGF) is presented. The hybrid method is applicable to inhomogeneous dielectric structures that are mutually coupled with wire antennas. The method employs the surface equivalence theorem in the discrete domain to separate the problem into a dielectric domain simulated using the FDTD method...
-
Evaluation of Gas Chromatography Stationary Phases Based on Morpholinium Ionic Liquids by McReynolds Constants and Activity Coefficients at Infinite Dilution
PublicationIn this work, four ionic liquids (ILs) based on the N-alkyl-N-methylmorpholinium cation ([Mor1,R], in which R = 2, 4, 8, or 10) and bis (trifluoromethanesulfonyl)imide anion were synthesized. Using GLC, a number of parameters describing the sorption properties of the investigated ILs were determined. The values of Kovats indices, McReynolds constants, and activity coefficients at infinite dilution were the basis for the evaluation...
-
Polynomial description of dynamic impedance spectrogram—introduction to a new impedance analysis method
PublicationThis paper presents a polynomial description of spectrograms obtained using Dynamic Electrochemical Impedance Spectroscopy. A method to fit the polynomial degree correctly is discussed. A simple electrical system of a diode connected in parallel with a capacitor was used for testing. Dynamic impedance measurements during potentiodynamic polarization were conducted. This paper presents an alternative analysis method that allows...