### 2-3 graphs which have Vizing's adjacency property.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number ${\left(\chi \u0305\right)}_{3CC}\left(G\right)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ${\left(\chi \u0305\right)}_{3CC}\left(G\right)\ge k$ for k = 3 and k = 4.

A $(0,2)$-graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0,\lambda )$-graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0,2)$-graph. $(0,2)$-graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0,\lambda )$-graphs and more specifically in $(0,2)$-graphs,...

Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v,w ∈ V (D), (u, v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D). This concept can be generalized as follows: A digraph is k-transitive if for every u, v ∈ V (D), the existence of a uv-directed path of length k in D implies that (u, v) ∈ A(D). A very useful structural characterization of transitive digraphs has been known for a long time, and...

A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150...

Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.

Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $\mathcal{L}$ of all shortest paths in $G$ is defined as the set of all paths $\xi $, then the lenght of $\xi $ does not exceed the length of $\varsigma $. While the definition of $\mathcal{L}$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of $\mathcal{L}$: a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...

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...

We characterize the class [...] L32 ${L}_{3}^{2}$ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 ${L}_{3}^{2}$ in the class of threshold graphs, where n is the number of vertices of a tested graph.

In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.