Displaying 21 – 40 of 715

Showing per page

A New Characterization of Unichord-Free Graphs

Terry A. McKee (2015)

Discussiones Mathematicae Graph Theory

Unichord-free graphs are defined as having no cycle with a unique chord. They have appeared in several papers recently and are also characterized by minimal separators always inducing edgeless subgraphs (in contrast to characterizing chordal graphs by minimal separators always inducing complete subgraphs). A new characterization of unichord-free graphs corresponds to a suitable reformulation of the standard simplicial vertex characterization of chordal graphs.

A new upper bound for the chromatic number of a graph

Ingo Schiermeyer (2007)

Discussiones Mathematicae Graph Theory

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 .

A Note on a Broken-Cycle Theorem for Hypergraphs

Martin Trinks (2014)

Discussiones Mathematicae Graph Theory

Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there

A note on cyclic chromatic number

Jana Zlámalová (2010)

Discussiones Mathematicae Graph Theory

A cyclic colouring of a graph G embedded in a surface is a vertex colouring of G in which any two distinct vertices sharing a face receive distinct colours. The cyclic chromatic number χ c ( G ) of G is the smallest number of colours in a cyclic colouring of G. Plummer and Toft in 1987 conjectured that χ c ( G ) Δ * + 2 for any 3-connected plane graph G with maximum face degree Δ*. It is known that the conjecture holds true for Δ* ≤ 4 and Δ* ≥ 18. The validity of the conjecture is proved in the paper for some special classes...

A note on face coloring entire weightings of plane graphs

Stanislav Jendrol, Peter Šugerek (2014)

Discussiones Mathematicae Graph Theory

Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3

A note on graph coloring

D. De Werra (1974)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A note on joins of additive hereditary graph properties

Ewa Drgas-Burchardt (2006)

Discussiones Mathematicae Graph Theory

Let L a denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set ( L a , ) is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in ( L a , ) has a finite or infinite family of minimal forbidden subgraphs.

A note on Möbius inversion over power set lattices

Klaus Dohmen (1997)

Commentationes Mathematicae Universitatis Carolinae

In this paper, we establish a theorem on Möbius inversion over power set lattices which strongly generalizes an early result of Whitney on graph colouring.

A Note on Neighbor Expanded Sum Distinguishing Index

Evelyne Flandrin, Hao Li, Antoni Marczyk, Jean-François Saclé, Mariusz Woźniak (2017)

Discussiones Mathematicae Graph Theory

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

Currently displaying 21 – 40 of 715