A graph-theoretical representation of PL-manifolds - A survey on crystallizations.
A New Characterization of Unichord-Free Graphs
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 proof of the four-colour theorem.
A new upper bound for the chromatic number of a graph
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 .
A Note on a Broken-Cycle Theorem for Hypergraphs
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 choosability in planar graphs
A note on chromatic number of direct product of graphs
A note on cyclic chromatic number
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 of G is the smallest number of colours in a cyclic colouring of G. Plummer and Toft in 1987 conjectured that 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 edge-colourings avoiding rainbow and monochromatic .
A note on face coloring entire weightings of plane graphs
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
A note on graph coloring extensions and list-colorings.
A note on graph colouring
A note on joins of additive hereditary graph properties
Let denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in has a finite or infinite family of minimal forbidden subgraphs.
A note on -free precolouring with colours.
A note on line colorings of cubic graphs
A note on maximal -degenerate graphs
A note on Möbius inversion over power set lattices
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
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.
A note on neighbour-distinguishing regular graphs total-weighting.