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 4 Next

Displaying 61 – 80 of 715

Showing per page

A Survey of the Path Partition Conjecture

Marietjie Frick (2013)

Discussiones Mathematicae Graph Theory

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.

A Tight Bound on the Set Chromatic Number

Jean-Sébastien Sereni, Zelealem B. Yilma (2013)

Discussiones Mathematicae Graph Theory

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.

A weighted graph polynomial from chromatic invariants of knots

Steven D. Noble, Dominic J. A. Welsh (1999)

Annales de l'institut Fourier

Motivated by the work of Chmutov, Duzhin and Lando on Vassiliev invariants, we define a polynomial on weighted graphs which contains as specialisations the weighted chromatic invariants but also contains many other classical invariants including the Tutte and matching polynomials. It also gives the symmetric function generalisation of the chromatic polynomial introduced by Stanley. We study its complexity and prove hardness results for very restricted classes of graphs.

About uniquely colorable mixed hypertrees

Angela Niculitsa, Vitaly Voloshin (2000)

Discussiones Mathematicae Graph Theory

A mixed hypergraph is a triple 𝓗 = (X,𝓒,𝓓) where X is the vertex set and each of 𝓒, 𝓓 is a family of subsets of X, the 𝓒-edges and 𝓓-edges, respectively. A k-coloring of 𝓗 is a mapping c: X → [k] such that each 𝓒-edge has two vertices with the same color and each 𝓓-edge has two vertices with distinct colors. 𝓗 = (X,𝓒,𝓓) is called a mixed hypertree if there exists a tree T = (X,𝓔) such that every 𝓓-edge and every 𝓒-edge induces a subtree of T. A mixed hypergraph 𝓗 is called uniquely...

Achromatic number of K 5 × K n for small n

Mirko Horňák, Štefan Pčola (2003)

Czechoslovak Mathematical Journal

The achromatic number of a graph G is the maximum number of colours in a proper vertex colouring of G such that for any two distinct colours there is an edge of G incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of K 5 and K n for all n ≤ 24 .

Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun, Min Chen (2020)

Czechoslovak Mathematical Journal

A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G . In other words, each cycle of G must be colored with at least three colors. Given a list assignment L = { L ( v ) : v ∈ V } , if there exists an acyclic coloring π of G such that π ( v ) ∈ L ( v ) for all v ∈ V , then we say that G is acyclically L -colorable. If G is acyclically L -colorable for any list assignment L with | L ( v ) | ≥ k for all v ∈ V , then G is acyclically k -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without 4-cycles...

Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree

Anna Fiedorowicz (2013)

Discussiones Mathematicae Graph Theory

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have...

Acyclic reducible bounds for outerplanar graphs

Mieczysław Borowiecki, Anna Fiedorowicz, Mariusz Hałuszczak (2009)

Discussiones Mathematicae Graph Theory

For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. G [ V i ] ∈ i for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that u ∈ V i and v ∈ V j is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring. If ⊆ R,...

Adjacent vertex distinguishing edge colorings of the direct product of a regular graph by a path or a cycle

Laura Frigerio, Federico Lastaria, Norma Zagaglia Salvi (2011)

Discussiones Mathematicae Graph Theory

In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.

Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six

Yuehua Bu, Ko-Wei Lih, Weifan Wang (2011)

Discussiones Mathematicae Graph Theory

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu, and J. Wang,...

Currently displaying 61 – 80 of 715