Random threshold graphs.
Realization of Hölder complexes
Simultaneous graph drawing: layout algorithms and visualization schemes.
Some news about oblique graphs
A k-gon α of a polyhedral graph G(V,E,F) is of type ⟨b₁,b₂,...,bₖ⟩ if the vertices incident with α in cyclic order have degrees b₁,b₂,...,bₖ and ⟨b₁,b₂,...,bₖ⟩ is the lexicographic minimum of all such sequences available for α. A polyhedral graph G is oblique if it has no two faces of the same type. Among others it is shown that an oblique graph contains vertices of degree 3.
Some Variations of Perfect Graphs
We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging...
Spatial graphs, knots and the cyclic polytope.
Splitting Cubic Circle Graphs
We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.
Stacks, queues and tracks: layouts of graph subdivisions.
Straight-line drawings of binary trees with linear area and arbitrary aspect ratio.
Straight-line drawings on restricted integer grids in two and three dimensions.
Strictly convex drawings of planar graphs.
Strongly pancyclic and dual-pancyclic graphs
Say that a cycle C almost contains a cycle C¯ if every edge except one of C¯ is an edge of C. Call a graph G strongly pancyclic if every nontriangular cycle C almost contains another cycle C¯ and every nonspanning cycle C is almost contained in another cycle C⁺. This is equivalent to requiring, in addition, that the sizes of C¯ and C⁺ differ by one from the size of C. Strongly pancyclic graphs are pancyclic and chordal, and their cycles enjoy certain interpolation and extrapolation properties with...
Symmetry of iteration graphs
We examine iteration graphs of the squaring function on the rings when , for a Fermat prime. We describe several invariants associated to these graphs and use them to prove that the graphs are not symmetric when and when and are symmetric when .
The arc-width of a graph.
The cost chromatic number and hypergraph parameters
In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.
The crossing number of a projective graph is quadratic in the face-width.
The maximum number of edges in a three-dimensional grid-drawing.
The representation of multi-hypergraphs by set intersections
This paper deals with weighted set systems (V,,q), where V is a set of indices, and the weight q is a nonnegative integer function on . The basic idea of the paper is to apply weighted set systems to formulate restrictions on intersections. It is of interest to know whether a weighted set system can be represented by set intersections. An intersection representation of (V,,q) is defined to be an indexed family of subsets of a set S such that for each E ∈ . A necessary condition for the existence...
The restricted arc-width of a graph.
The structure of plane graphs with independent crossings and its applications to coloring problems
If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is...