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-10 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ł
Wyświetlanie 1-10 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