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ę "chromatic number" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 81
Tytuł:
Unified Spectral Bounds on the Chromatic Number
Autorzy:
Elphick, Clive
Wocjan, Pawel
Powiązania:
https://bibliotekanauki.pl/articles/31234065.pdf
Data publikacji:
2015-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
majorization
Opis:
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where μ1 and μn are respectively the maximum and minimum eigenvalues of the adjacency matrix: χ ≥ 1+μ1/−μn. We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 773-780
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Tight Bound on the Set Chromatic Number
Autorzy:
Sereni, Jean-Sébastien
Yilma, Zelealem B.
Powiązania:
https://bibliotekanauki.pl/articles/30146528.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
set coloring
set chromatic number
neighbor
distinguishing coloring
Opis:
We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 461-465
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Chromatic Properties of the Pancake Graphs
Autorzy:
Konstantinova, Elena
Powiązania:
https://bibliotekanauki.pl/articles/31341647.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Pancake graph
Cayley graphs
symmetric group
chromatic number
total chromatic number
Opis:
Chromatic properties of the Pancake graphs Pn, n ⩾ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are investigated in the paper. It is proved that for any n ⩾ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n − 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks’ bound for n ⩾ 7 and Katlin’s bound for n ⩽ 28. Algorithms of a total n-coloring and a proper (n − 1)-coloring are given.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 777-787
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distinguishing graphs by the number of homomorphisms
Autorzy:
Fisk, Steve
Powiązania:
https://bibliotekanauki.pl/articles/971917.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph homomorphism
chromatic number
Opis:
A homomorphism from one graph to another is a map that sends vertices to vertices and edges to edges. We denote the number of homomorphisms from G to H by |G → H|. If is a collection of graphs, we say that distinguishes graphs G and H if there is some member X of such that |G → X | ≠ |H → X|. is a distinguishing family if it distinguishes all pairs of graphs.
We show that various collections of graphs are a distinguishing family.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 1; 73-75
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On maximal finite antichains in the homomorphism order of directed graphs
Autorzy:
Nesetril, Jaroslav
Tardif, Claude
Powiązania:
https://bibliotekanauki.pl/articles/743175.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
homomorphism duality
Opis:
We show that the pairs ${T,D_T}$ where T is a tree and $D_T$ its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 325-332
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge colorings and total colorings of integer distance graphs
Autorzy:
Kemnitz, Arnfried
Marangio, Massimiliano
Powiązania:
https://bibliotekanauki.pl/articles/743555.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
integer distance graph
chromatic number
choice number
chromatic index
choice index
total chromatic number
total choice number
Opis:
An integer distance graph is a graph G(D) with the set Z of integers as vertex set and two vertices u,v ∈ Z are adjacent if and only if |u-v| ∈ D where the distance set D is a subset of the positive integers N. In this note we determine the chromatic index, the choice index, the total chromatic number and the total choice number of all integer distance graphs, and the choice number of special integer distance graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 149-158
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Survey on Packing Colorings
Autorzy:
Brešar, Boštjan
Ferme, Jasmina
Klavžar, Sandi
Rall, Douglas F.
Powiązania:
https://bibliotekanauki.pl/articles/31804166.pdf
Data publikacji:
2020-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
packing coloring
packing chromatic number
subcubic graph
S -packing chromatic number
computational complexity
Opis:
If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1, X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ ∪ Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai = i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and its generalization, the S-packing coloring. We also list several conjectures and open problems.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 923-970
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Conditions for β-perfectness
Autorzy:
Keijsper, Judith
Tewes, Meike
Powiązania:
https://bibliotekanauki.pl/articles/743553.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
colouring number
polynomial time
Opis:
A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily).
The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs, for a graph to be β-perfect. We give new sufficient conditions and make improvements to sufficient conditions previously given by others. We also mention a necessary condition which generalizes the fact that no β-perfect graph contains an even hole.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 123-148
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Coloring Some Finite Sets in $ \mathbb{R}^n $
Autorzy:
Balogh, József
Kostochka, Alexandr
Raigorodskii, Andrei
Powiązania:
https://bibliotekanauki.pl/articles/30146863.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
independence number
distance graph
Opis:
This note relates to bounds on the chromatic number $ \chi (\mathbb{R}^n)$ of the Euclidean space, which is the minimum number of colors needed to color all the points in $ \mathbb{R}^n$ so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs $ G_n $ in $ \mathbb{R}_n $ was introduced showing that $ \chi(\mathbb{R}^n) \ge \chi(G_n) \ge (1+ o(1))\frac{n^2}{6} $. For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that $ \chi(G_n) \sim \frac{n^2}{6} $ and find an exact formula for the chromatic number in the case of $ n = 2^k $ and $ n = 2^k − 1 $.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 25-31
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ł:
Bounds for the b-Chromatic Number of Subgraphs and Edge-Deleted Subgraphs
Autorzy:
Francis, P.
Raj, S. Francis
Powiązania:
https://bibliotekanauki.pl/articles/31340595.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
b-coloring
b-chromatic number
Opis:
A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $ b(G) $ of $ G $. In this paper, we obtain bounds for the $b$- chromatic number of induced subgraphs in terms of the $b$-chromatic number of the original graph. This turns out to be a generalization of the result due to R. Balakrishnan et al. [Bounds for the b-chromatic number of G−v, Discrete Appl. Math. 161 (2013) 1173-1179]. Also we show that for any connected graph $G$ and any $ e \in E(G) $, $ b(G - e) ≤ b(G) + \ceil{ n/2 } - 2 $. Further, we determine all graphs which attain the upper bound. Finally, we conclude by finding bound for the $b$-chromatic number of any subgraph.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 959-976
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
T-Colorings, Divisibility and the Circular Chromatic Number
Autorzy:
Janczewski, Robert
Trzaskowska, Anna Maria
Turowski, Krzysztof
Powiązania:
https://bibliotekanauki.pl/articles/32083881.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
circular chromatic number
T-coloring
Opis:
Let $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 $esp_T(G)$ and $esp_{d⊙T}(G)$, where $d$ is a positive integer and \[d⊙T=\{ 0≤t≤d(maxT+1):d|t⇒t/d∈T\}.\] We show that $esp_{d⊙T}(G) = d esp_T(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 \[esp_{d⊙\{0\}}(G)=⌈d(χ_c(G)-1)⌉,\] where $χ_c(G)$ is the circular chromatic number of $G$. This result allows us to formulate several interesting conclusions that include a new formula for the circular chromatic number \[χ_c(G)=1+inf\{esp_{d⊙\{0\}}(G)/d:d≥1\}\] and a proof that the formula for the $T$-edge span of powers of cycles, stated as conjecture in [Y. Zhao, W. He and R. Cao, The edge span of T-coloring on graph $C_n^d$, Appl. Math. Lett. 19 (2006) 647–651], is true.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 441-450
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
General multiplicative Zagreb indices of graphs with given clique number
Autorzy:
Vetrik, Tomas
Balachandran, Selvaraj
Powiązania:
https://bibliotekanauki.pl/articles/255259.pdf
Data publikacji:
2019
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
clique number
multiplicative Zagreb index
chromatic number
Opis:
We obtain lower and upper bounds on general multiplicative Zagreb indices for graphs of given clique number and order. Bounds on the basic multiplicative Zagreb indices and on the multiplicative sum Zagreb index follow from our results. We also determine graphs with the smallest and the largest indices.
Źródło:
Opuscula Mathematica; 2019, 39, 3; 433-446
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The s-packing chromatic number of a graph
Autorzy:
Goddard, Wayne
Xu, Honghai
Powiązania:
https://bibliotekanauki.pl/articles/743305.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
coloring
packing
broadcast chromatic number
Opis:
Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to {1,2,...,k} such that vertices with color i have pairwise distance greater than $a_i$, and the S-packing chromatic number $χ_S(G)$ of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on the parameter and its relationship with other parameters. We characterize the graphs with $χ_S = 2$ and determine $χ_S$ for several common families of graphs. We examine $χ_S$ for the infinite path and give some exact values and asymptotic bounds. Finally we consider complexity questions, especially about recognizing graphs with $χ_S = 3$.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 795-806
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Efficient coloring of chordless graphs
Autorzy:
Janczewski, R.
Małafiejski, M.
Powiązania:
https://bibliotekanauki.pl/articles/375900.pdf
Data publikacji:
2009
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
vertex coloring
chordless graphs
chromatic number
Opis:
We are given a simple graph G = (V,E). Any edge e ∈ E is a chord in a path P ⊆ G (cycle C ⊆ G) iff a graph obtained by joining e to path P (cycle C) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call pathchordless (cycle-chordless). We will prove that recognizing and coloring of these graphs can be done in O(n2) and O(n) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.
Źródło:
Decision Making in Manufacturing and Services; 2009, 3, 1-2; 5-14
1896-8325
2300-7087
Pojawia się w:
Decision Making in Manufacturing and Services
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 81

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