Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "graph coloring" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 95
Tytuł:
Generalized colorings and avoidable orientations
Autorzy:
Szigeti, Jenő
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/971967.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property
graph coloring
Opis:
Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 137-145
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Frequency planning and ramifications of coloring
Autorzy:
Eisenblätter, Andreas
Grötschel, Martin
Koster, Arie
Powiązania:
https://bibliotekanauki.pl/articles/743541.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
frequency assignment
graph coloring
Opis:
This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful.The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue.Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand vertices and range form rather sparse to almost complete.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 51-88
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analogues of cliques for oriented coloring
Autorzy:
Klostermeyer, William
MacGillivray, Gary
Powiązania:
https://bibliotekanauki.pl/articles/744524.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
oriented coloring
clique
planar graph
Opis:
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 373-387
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Choice-Perfect Graphs
Autorzy:
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/30146654.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
list coloring
choice-perfect graph
Opis:
Given a graph $ G = (V,E) $ and a set $ L_v $ of admissible colors for each vertex $ v \in V $ (termed the list at $v$), a list coloring of $G$ is a (proper) vertex coloring $ \phi : V \rightarrow \bigcup \text{}_{v \in V} L_v $ such that $ \phi (v) \in L_v $ for all $ v \in V $ and $ \phi(u) \ne \phi(v) $ for all $ uv \in E $. If such a $ \phi $ exists, $G$ is said to be list colorable. The choice number of $G$ is the smallest natural number $k$ for which $G$ is list colorable whenever each list contains at least $k$ colors. In this note we initiate the study of graphs in which the choice number equals the clique number or the chromatic number in every induced subgraph. We call them choice-ω-perfect and choice-χ-perfect graphs, respectively. The main result of the paper states that the square of every cycle is choice-χ-perfect.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 231-242
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Contemporary Methods for Graph Coloring as an Example of Discrete Optimization
Autorzy:
Bilski, Adrian
Powiązania:
https://bibliotekanauki.pl/articles/226705.pdf
Data publikacji:
2019
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
graph coloring
chromatic number
metaheuristics
Opis:
This paper provides an insight into graph coloring application of the contemporary heuristic methods. It discusses a variety of algorithmic solutions for The Graph Coloring Problem (GCP) and makes recommendations for implementation. The GCP is the NP-hard problem, which aims at finding the minimum number of colors for vertices in such a way, that none of two adjacent vertices are marked with the same color.With the advent of multicore processing technology, the metaheuristic approach to solving GCP reemerged as means of discrete optimization. To explain the phenomenon of these methods, the author makes a thorough survey of AI-based algorithms for GCP, while pointing out the main differences between all these techniques.
Źródło:
International Journal of Electronics and Telecommunications; 2019, 65, 2; 235-243
2300-1933
Pojawia się w:
International Journal of Electronics and Telecommunications
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
List Star Edge-Coloring of Subcubic Graphs
Autorzy:
Kerdjoudj, Samia
Kostochka, Alexandr
Raspaud, André
Powiązania:
https://bibliotekanauki.pl/articles/31342241.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
edge coloring
star coloring
planar graphs
Opis:
A star edge-coloring of a graph $ G $ is a proper edge coloring such that every 2-colored connected subgraph of $ G $ is a path of length at most 3. For a graph $ G $, let the list star chromatic index of $ G $, $ ch_{st}^' (G) $, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph $G$ is less than \( \tfrac{7}{3} \) (respectively, \( \tfrac{5}{2} \)), then $ ch_{st}^' (G) \le 5 $ (respectively, $ ch_{st}^' (G) \le 6 $).
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1037-1054
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph
Autorzy:
Mojdeh, D.
Powiązania:
https://bibliotekanauki.pl/articles/743869.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
defining set
cartesian product
Opis:
In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c).
The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G = Cₘ × Kₙ, c) with c > χ(G), where n ≥ 2 and m ≥ 3, unless the defining number $d(K₃×C_{2r},4)$, which is given an upper and lower bounds for this defining number. Also some bounds of defining number are introduced.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 59-72
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
3-consecutive c-colorings of graphs
Autorzy:
Bujtás, Csilla
Sampathkumar, E.
Tuza, Zsolt
Subramanya, M.
Dominic, Charles
Powiązania:
https://bibliotekanauki.pl/articles/744032.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
vertex coloring
consecutive coloring
upper chromatic number
Opis:
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number $(χ̅)_{3CC}(G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with $(χ̅)_{3CC}(G) ≥ k$ for k = 3 and k = 4.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 393-405
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on the Equitable Choosability of Complete Bipartite Graphs
Autorzy:
Mudrock, Jeffrey A.
Chase, Madelynn
Thornburgh, Ezekiel
Kadera, Isaac
Wagstrom, Tim
Powiązania:
https://bibliotekanauki.pl/articles/32325306.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
equitable coloring
list coloring
equitable choos-ability
Opis:
In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A k-assignment, L, for a graph G assigns a list, L(v), of k available colors to each v ∈ V (G), and an equitable L-coloring of G is a proper coloring, f, of G such that f(v) ∈ L(v) for each v ∈ V (G) and each color class of f has size at most ⌈|V (G)|/k⌉. Graph G is said to be equitably k-choosable if an equitable L-coloring of G exists whenever L is a k-assignment for G. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies Kn,m is equitably k-choosable if k ≥ max{n, m} provided Kn,m ≠ K2l+1,2l+1. We prove Kn,m is equitably k-choosable if m ≤ ⌈ (m + n)/k⌉ (k − n) which gives Kn,m is equitably k-choosable for certain k satisfying k < max{n, m}. We also give a complete characterization of the equitable choosability of complete bipartite graphs that have a partite set of size at most 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1091-1101
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph Classes Generated by Mycielskians
Autorzy:
Borowiecki, Mieczys law
Borowiecki, Piotr
Drgas-Burchardt, Ewa
Sidorowicz, Elżbieta
Powiązania:
https://bibliotekanauki.pl/articles/31348089.pdf
Data publikacji:
2020-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Mycielski graphs
graph coloring
chromatic number
Opis:
In 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 of order $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 chromatic number of the subgraph induced by all vertices that belong to at least one triangle is at most $p$. We also address the problem of characterizing the latter class in terms of forbidden graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1163-1173
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On List Equitable Total Colorings of the Generalized Theta Graph
Autorzy:
Mudrock, Jeffrey A.
Marsh, Max
Wagstrom, Tim
Powiązania:
https://bibliotekanauki.pl/articles/32326107.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
total coloring
equitable coloring
list coloring
equitable choosability
Opis:
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A k-assignment, L, for a graph G assigns a list, L(v), of k available colors to each v ∈ V (G), and an equitable L-coloring of G is a proper coloring, f, of G such that f(v) ∈ L(v) for each v ∈ V (G) and each color class of f has size at most ⌈|V (G)|/k⌉. Graph G is equitably k-choosable if G is equitably L-colorable whenever L is a k-assignment for G. In 2018, Kaul, Mudrock, and Pelsmajer subsequently introduced the List Equitable Total Coloring Conjecture which states that if T is a total graph of some simple graph, then T is equitably k-choosable for each k ≥ max{xℓ(T), Δ(T)/2 + 2} where Δ(T) is the maximum degree of a vertex in T and xℓ(T ) is the list chromatic number of T. In this paper, we verify the List Equitable Total Coloring Conjecture for subdivisions of stars and the generalized theta graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1215-1233
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On-line -coloring of graphs
Autorzy:
Borowiecki, Piotr
Powiązania:
https://bibliotekanauki.pl/articles/743585.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
on-line algorithm
graph coloring
hereditary property
Opis:
For a given induced hereditary property , a -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 . We consider the effectiveness of on-line -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 of any stingy on-line -coloring algorithm. In the class of generalized trees, we characterize graphs critical for the greedy -coloring. A class of graphs for which a greedy algorithm always generates optimal -colorings for the property = K₃-free is given.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 3; 389-401
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
Autorzy:
Dong, Aijun
Zhang, Xin
Powiązania:
https://bibliotekanauki.pl/articles/31342275.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
equitable choosability
maximum average degree
Opis:
A graph is said to be equitably $k$-colorable if the vertex set $V (G)$ can be partitioned into $k$ independent subsets $ V_1, V_2, . . ., V_k $ such that $ | | V_i |−| V_j | | \le 1 $ $(1 \le i, j \le k) $. A graph $G$ is equitably $k$-choosable if, for any given $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $ \ceil{ \frac{|V(G)|}{ k } } $ vertices. In this paper, we prove that if $G$ is a graph such that $ mad(G) < 3 $, then $G$ is equitably $k$-colorable and equitably $k$- choosable where $ k \ge \text{max} \{ \Delta (G), 4 \} $. Moreover, if $G$ is a graph such that $ mad(G) < \frac{12}{5} $, then $G$ is equitably $k$-colorable and equitably $k$-choosable where $ k \ge \text{max} \{ \Delta (G), 3 \} $.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 829-839
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
L(2, 1)-Labeling of Circulant Graphs
Autorzy:
Mitra, Sarbari
Bhoumik, Soumya
Powiązania:
https://bibliotekanauki.pl/articles/31343649.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
L(2
1)-labeling
circulants
Opis:
An $L(2, 1)$-labeling of a graph $ \Gamma $ is an assignment of non-negative integers to the vertices such that adjacent vertices receive labels that differ by at least 2, and those at a distance of two receive labels that differ by at least one. Let $ \lambda_2^1 (\Gamma) $ denote the least $ \lambda $ such that $ \Gamma $ admits an $ L(2, 1) $-labeling using labels from $ \{ 0, 1, . . ., \lambda \} $. A Cayley graph of group $G$ is called a circulant graph of order $n$, if $ G = \mathbb{Z}_n$. In this paper initially we investigate the upper bound for the span of the $L(2, 1)$-labeling for Cayley graphs on cyclic groups with “large” connection sets. Then we extend our observation and find the span of $L(2, 1)$-labeling for any circulants of order $n$.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 143-155
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The NP-completeness of automorphic colorings
Autorzy:
Mazzuoccolo, Giuseppe
Powiązania:
https://bibliotekanauki.pl/articles/744108.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
NP-complete problems
chromatic parameters
graph coloring
computational complexity
Opis:
Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 705-710
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 95

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies