Search
Search results for: HYPERGRAPH EDGE-COLORING
-
Optimal edge-coloring with edge rate constraints
PublicationWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Interval Edge-Coloring of Graphs
Publication -
Mixed graph edge coloring
PublicationW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
Interval edge-coloring of graphs.
PublicationRozdział poświęcony prezentacji modelu zwartego kolorowania krawędziowego grafów i jego znanych własności. Szczególny nacisk położono na opis klas grafów dających się pokolorować zwarcie w czasie wielomianowym. Omówiono także stratność jako miarę niepodatności grafu na kolorowanie zwarte.
-
Edge-coloring of 3-uniform hypergraphs
PublicationWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
Interval edge coloring of a graph with forbidden colors
Publication -
Self-stabilizing algorithm for edge-coloring of graphs
PublicationReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
A linear time algorithm for edge coloring of binomial trees
Publication -
Edge coloring of graphs of signed class 1 and 2
PublicationRecently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublicationRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Towards the boundary between easy and hard control problems in multicast Clos networks
PublicationIn this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially...
-
A bound on the number of middle-stage crossbars in f-cast rearrangeable Clos networks
PublicationIn 2006 Chen and Hwang gave a necessary and sufficient condition under which a three-stage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fan-out property, we give similar conditions for f-cast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. high-speed crossconnects....
-
Dataset of non-isomorphic graphs being coloring types (K5-e,Km-e;n), 2<m<5, 1<n<R(K5-e,Km-e)
Open Research DataFor K5-e and Km-e graphs, the type coloring (K5-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K5-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K5-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs being coloring types (K6-e,Km-e;n), 2<m<5, 1<n<R(K6-e,Km-e)
Open Research DataFor K6-e and Km-e graphs, the type coloring (K6-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K6-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed. The Ramsey number R(K6-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs of the coloring types (K4,K4;n), 1<n<R(4,4)
Open Research DataFor K4 graph, a coloring type (K4,K4;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the K4 subgraph in the second color (representing by edges in the graph).The Ramsey number R(4,4) is the smallest natural number n such that for any edge coloring of...
-
Dataset of non-isomorphic graphs being coloring types (K3-e,Km-e;n), 2<m<8, 1<n<R(K3-e,Km-e)
Open Research DataFor K3-e and Km-e graphs, the type coloring (K3-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs being coloring types (K4-e,Km-e;n), 2<m<7, 1<n<R(K4-e,Km-e)
Open Research DataFor K4-e and Km-e graphs, the type coloring (K4-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4-e,Km-e) is the smallest...
-
Equitable coloring of hypergraphs
PublicationA hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km-e;n), 2<m<7, 1<n<R(K3,Km-e).
Open Research DataFor K3 and Km-e graphs, a coloring type (K3,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3,Km-e)...
-
Dataset of non-isomorphic graphs of the coloring types (Km,K3-e;n), 4<m<8, 1<n<R(Km,K3-e)
Open Research DataFor Km and K3-e graphs, a coloring type (Km,K3-e;n) is such an edge coloring of the full Kn graph, which does not have the Km subgraph in the first color (representing by no edges in the graph) or the K3-e subgraph in the second color (representing by edges in the graph). K3-e means the full Km graph with one edge removed.The Ramsey number R(Km,K3-e)...
-
Dataset of non-isomorphic graphs of the coloring types (K4,Km-e;n), 2<m<5, 1<n<R(K4,Km-e)
Open Research DataFor K4 and Km-e graphs, a coloring type (K4,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4,Km-e)...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km;n), 2<m<7, 1<n<R(3,m)
Open Research DataFor K3 and Km graphs, a coloring type (K3,Km;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km subgraph in the second color (representing by edges in the graph).The Ramsey number R(3,m) is the smallest natural number n such that for any edge coloring...
-
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.
-
The Backbone Coloring Problem for Bipartite Backbones
PublicationLet G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
-
Independence in uniform linear triangle-free hypergraphs
PublicationThe independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
-
No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublicationIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...
-
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),...
-
Rearrangeability in multicast Clos networks is NP-complete
PublicationPrzestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite...
-
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) =...
-
Weighted 2-sections and hypergraph reconstruction
PublicationIn the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed...
-
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...
-
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...
-
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...
-
On-line P-coloring of graphs
PublicationFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
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.
-
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...
-
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...
-
Interval incidence graph coloring
PublicationIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
-
Interval incidence coloring of subcubic graphs
PublicationIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
Interval incidence coloring of bipartite graphs
PublicationIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
-
Leading Edge
Journals -
Dynamic F-free Coloring of Graphs
PublicationA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
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.
-
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...
-
Global edge alliances in graphs
PublicationIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
PublicationGiven a graph G= (V, E), the subdivision of an edge e=uv∈E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions...
-
Parallel tabu search for graph coloring problem
PublicationTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
-
Chromatic cost coloring of weighted bipartite graphs
PublicationGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
On minimum cost edge searching
PublicationWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...