A categorification for the chromatic polynomial.
A characterization of graphs in which some minimum dominating set covers all the edges
A characterization of locating-total domination edge critical graphs
For a graph G = (V,E) without isolated vertices, a subset D of vertices of V is a total dominating set (TDS) of G if every vertex in V is adjacent to a vertex in D. The total domination number γₜ(G) is the minimum cardinality of a TDS of G. A subset D of V which is a total dominating set, is a locating-total dominating set, or just a LTDS of G, if for any two distinct vertices u and v of V(G)∖D, . The locating-total domination number is the minimum cardinality of a locating-total dominating set...
A class of 4-pseudomanifolds similar to the lense spaces.
A class of tight circulant tournaments
A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.
A class of weakly perfect graphs
A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.
A classification for maximal nonhamiltonian Burkard-Hammer graphs
A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G+uv is...
A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture
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.
A decomposition of gallai multigraphs
An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees...
A Different Short Proof of Brooks’ Theorem
Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.
A generalization of combinatorial Nullstellensatz.
A generalization of the dichromatic polynomial of a graph.
A genus for N-dimensional knots and links.
A geometric theory of hypergraph colouring.
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