All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 34 Next

Displaying 661 – 680 of 719

Showing per page

The use of Euler's formula in (3,1)*-list coloring

Yongqiang Zhao, Wenjie He (2006)

Discussiones Mathematicae Graph Theory

A graph G is called (k,d)*-choosable if, for every list assignment L satisfying |L(v)| = k for all v ∈ V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. Ko-Wei Lih et al. used the way of discharging to prove that every planar graph without 4-cycles and i-cycles for some i ∈ 5,6,7 is (3,1)*-choosable. In this paper, we show that if G is 2-connected, we may just use Euler’s formula and the graph’s structural properties to prove...

The Vertex-Rainbow Index of A Graph

Yaping Mao (2016)

Discussiones Mathematicae Graph Theory

The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤...

Three edge-coloring conjectures

Richard H. Schelp (2002)

Discussiones Mathematicae Graph Theory

The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.

Torsion in graph homology

Laure Helme-Guizon, Józef H. Przytycki, Yongwu Rong (2006)

Fundamenta Mathematicae

Khovanov homology for knots has generated a flurry of activity in the topology community. This paper studies the Khovanov type cohomology for graphs with a special attention to torsion. When the underlying algebra is ℤ[x]/(x²), we determine precisely those graphs whose cohomology contains torsion. For a large class of algebras, we show that torsion often occurs. Our investigation of torsion led to other related general results. Our computation could potentially be used to predict the Khovanov-Rozansky...

Unified Spectral Bounds on the Chromatic Number

Clive Elphick, Pawel Wocjan (2015)

Discussiones Mathematicae Graph Theory

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...

Unique factorization theorem

Peter Mihók (2000)

Discussiones Mathematicae Graph Theory

A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let ₁,₂, ...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable (G has property ₁ º₂ º... ºₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph G [ V i ] of G induced by Vi belongs to i ; i = 1,2,...,n. A property is said to be reducible...

Unique factorization theorem for object-systems

Peter Mihók, Gabriel Semanišin (2011)

Discussiones Mathematicae Graph Theory

The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal...

Currently displaying 661 – 680 of 719