Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 22

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  chromatic number
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Distinguishing graphs by the number of homomorphisms

100%
Fisk S.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
73-75
EN
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On maximal finite antichains in the homomorphism order of directed graphs

100%
Nesetril J., Tardif C.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
325-332
EN
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.
3
Content available remote

Unified Spectral Bounds on the Chromatic Number

100%
Elphick C., Wocjan P.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
773-780
EN
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Distance perfectness of graphs

80%
Włoch A.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 1
31-43
EN
In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].
5
Content available remote

Coloring Some Finite Sets in ℝn

80%
Balogh J., Kostochka A., Raigorodskii A.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
25-31
EN
This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of n = 2k and n = 2k − 1.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Conditions for β-perfectness

80%
Keijsper J., Tewes M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
123-148
EN
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.
7
Content available remote

The Chromatic Number of Random Intersection Graphs

80%
Rybarczyk K.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
465-476
EN
We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A new upper bound for the chromatic number of a graph

80%
Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
137-142
EN
Let G be a graph of order n with clique number ω(G), chromatic number χ(G) and independence number α(G). We show that χ(G) ≤ [(n+ω+1-α)/2]. Moreover, χ(G) ≤ [(n+ω-α)/2], if either ω + α = n + 1 and G is not a split graph or α + ω = n - 1 and G contains no induced $K_{ω+3}- C₅$.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Bounds on the global offensive k-alliance number in graphs

80%
Chellali M., Haynes T., Randerath B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
597-613
EN
Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $γₒ^k(G)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $γₒ^k(G)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Coloring rectangular blocks in 3-space

80%
Magnant C., Martin D.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
161-170
EN
If rooms in an office building are allowed to be any rectangular solid, how many colors does it take to paint any configuration of rooms so that no two rooms sharing a wall or ceiling/floor get the same color? In this work, we provide a new construction which shows this number can be arbitrarily large.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Vertex coloring the square of outerplanar graphs of low degree

80%
Agnarsson G., Halldórsson M.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
619-636
EN
Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture

80%
Haddad L., Tardif C.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
545-549
EN
The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Colouring graphs with prescribed induced cycle lengths

71%
Randerath B., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
267-281
EN
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is $𝓖^I(4,5)$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of $𝓖^I(4,5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every $G ∈ 𝓖^I(n₁,n₂)$ with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class $𝓖^I(n₁,n₂)$. Here we obtain the surprising result that there exists no linear χ-binding function for $𝓖^I(3,4)$.
14
Content available remote

A Tight Bound on the Set Chromatic Number

71%
Sereni J.-S., Yilma Z. B.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
461-465
EN
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.
15
Content available remote

On Generalized Sierpiński Graphs

71%
Rodríguez-Velázquez J. A., Rodríguez-Bazan E. D., Estrada-Moreno A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
547-560
EN
In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
16
Content available remote

Chromatic Properties of the Pancake Graphs

71%
Konstantinova E.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
777-787
EN
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.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized matrix graphs and completely independent critical cliques in any dimension

71%
Lattanzio J., Zheng Q.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 3
583-602
EN
For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent critical cliques for any k, where k ≥ 2. Some attention is given to this application and its relationship with the double-critical conjecture that the only vertex double-critical graph is the complete graph.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some maximum multigraphs and edge/vertex distance colourings

61%
Skupień Z.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
89-106
EN
Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge colorings and total colorings of integer distance graphs

61%
Kemnitz A., Marangio M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
149-158
EN
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.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graph colorings with local constraints - a survey

61%
Tuza Z.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
161-228
EN
We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_v$ for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality $c_v$ for each vertex in such a way that the sets C(v),C(v') are disjoint for each pair v,v' of adjacent vertices. The particular case of constant |L(v)| with $c_v$ = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. To illustrate typical techniques, some of the proofs are sketched.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.