Characterizing symmetric diametrical graphs of order 12 and diameter 4.
Choice-Perfect Graphs
Given a graph G = (V,E) and a set Lv of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → S v2V Lv such that ϕ(v) ∈ Lv for all v ∈ V and ϕ(u) 6= ϕ(v) for all uv ∈ E. If such a ϕ exists, G is said to be list colorable. The choice number of G is the smallest natural number k for which G is list colorable whenever each list contains at least k colors. In this note we initiate the study of graphs in which the choice number equals...
Chordal intersection graphs of bands
Circularity of graphs and continua: topology
Classes of graphs definable by graph algebra identities or quasi-identities
Classes of graphs with restricted interval models.
Clique graph representations of ptolemaic graphs
A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special...
Clique-width and the speed of hereditary properties.
Coalescence of difans and diwheels.
Colouring graphs with prescribed induced cycle lengths
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...
Cores and shells of graphs
The -core of a graph , , is the maximal induced subgraph such that , if it exists. For , the -shell of a graph is the subgraph of induced by the edges contained in the -core and not contained in the -core. The core number of a vertex is the largest value for such that , and the maximum core number of a graph, , is the maximum of the core numbers of the vertices of . A graph is -monocore if . This paper discusses some basic results on the structure of -cores and -shells....
Countable splitting graphs
A graph is called splitting if there is a 0-1 labelling of its vertices such that for every infinite set C of natural numbers there is a sequence of labels along a 1-way infinite path in the graph whose restriction to C is not eventually constant. We characterize the countable splitting graphs as those containing a subgraph of one of three simple types.
Covering graphs and subdirect decompositions of partially ordered sets
Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties
Let ₁,₂,...,ₙ be graph properties, a graph G is said to be uniquely (₁,₂, ...,ₙ)-partitionable if there is exactly one (unordered) partition V₁,V₂,...,Vₙ of V(G) such that for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if and are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ 1,2,...,n.
Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group
Let V be a finite vertex set and let (, +) be a finite abelian group. An -labeled and reversible 2-structure defined on V is a function g : (V × V) (v, v) : v ∈ V → such that for distinct u, v ∈ V, g(u, v) = −g(v, u). The set of -labeled and reversible 2-structures defined on V is denoted by ℒ(V, ). Given g ∈ ℒ(V, ), a subset X of V is a clan of g if for any x, y ∈ X and v ∈ V X, g(x, v) = g(y, v). For example, ∅, V and v (for v ∈ V) are clans of g, called trivial. An element g of ℒ(V, ) is primitive...
Decomposition of complete graphs into factors of diameter two
Decomposition tree and indecomposable coverings
Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and {x}, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called...
Degree Sequences of Monocore Graphs
A k-monocore graph is a graph which has its minimum degree and degeneracy both equal to k. Integer sequences that can be the degree sequence of some k-monocore graph are characterized as follows. A nonincreasing sequence of integers d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min {n − 1, k + n − i} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .
Die Minimalbasis der Menge aller nicht in die projektive Ebene einbettbaren Graphen.
Digraphs with large exponent.