Local condition for planar graphs of maximum degree 7 to be 8-totally colorable

The total chromatic number of a graph G, denoted by χ^″(G), is the minimum number of colors needed to color the vertices and edges of G such that no two adjacent or incident elements get the same color. It is known that if a planar graph G has maximum degree Δ≥9, then χ^″(G)=Δ+1. In this paper, we prove that if G is a planar graph with maximum degree 7, and for every vertex v, there is an integer k_v∈{3,4,5,6} so that v is not incident with any k_v-cycle, then χ^″(G)=8.     

Linear choosability of graphs

A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

Two-factors in orientated graphs with forbidden transitions

The instance of the problem of finding 2-factors in an orientated graph with forbidden transitions consists of an orientated graph G and for each vertex v of G, a graph H_v of allowed transitions at v. Vertices of the graph H_v are the edges incident to v. An orientated 2-factor F of G is called legal if all the transitions are allowed, i.e. for every vertex v, the two edges of F adjacent to it form an edge in H_v. Deciding whether a legal 2-factor exists in G is NP-complete in general. We investigate the case when the graphs of allowed transitions are taken from some fixed class C. We provide an exact characterization of classes C so that the problem is NP-complete. In particular, we prove a dichotomy for this problem, i.e. that for any class C it is either polynomial or NP-complete.     

Circular vertex arboricity

The vertex arboricity va(G) of graph G is defined as the minimum of subsets in a partition of the vertex set of G so that each subset induces an acyclic subgraph and has been widely studied. We define the concept of circular vertex arboricity va_c(G) of graph G, which is a natural generalization of vertex arboricity. We give some basic properties of circular vertex arboricity and study the circular vertex arboricity of planar graphs.     

The interval number of a planar graph: Three intervals suffice

Suppose each vertex of a graph G is assigned a subset of the real line consisting of at most t closed intervals. This assignment is called a t-interval representation of G when vertex v is adjacent to vertex w if and only if some interval for v intersects some interval for w. The interval number i(G) of a graph G is the smallest number t such that G has a t-interval representation. It is proved that i(G) ≤ 3 whenever G is planar and that this bound is the best possible. The related concepts of displayed interval number and depth-r interval number are discussed and their maximum values for certain classes of planar graphs are found.     

Color degree and alternating cycles in edge-colored graphs

Let G be an edge-colored graph. An alternating cycle of G is a cycle of G in which any two consecutive edges have distinct colors. Let d^c(v), the color degree of a vertex v, be defined as the maximum number of edges incident with v that have distinct colors. In this paper, we study color degree conditions for the existence of alternating cycles of prescribed length.     

The heterochromatic cycles in edge-colored graphs

Given a graph and an edge coloring C of G, a heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be the maximum number of distinct colored edges incident with v. In this paper, we give several sufficient conditions for the existence of heterochromatic cycles in edge-colored graphs.     

Diameter-essential edges in a graph

The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity among the vertices of G. The contraction of edge e=uv in G consists of removing e and identifying u and v as a single new vertex w, where w is adjacent to any vertex that at least one of u or v were adjacent to. The graph resulting from contracting edge e is denoted G/e. An edge e is diameter-essential if diam(G/e)<diam(G). Let c(G) denote the number of diameter-essential edges in graph G. In this paper, we study existence and extremal problems for c(G); determine bounds on c(G) in terms of diameter and order; and obtain characterizations of graphs achieving extreme values of c(G).     

Fundamental group and cycle space of dual graphs and applications

In this work, we study the fundamental group of dual graph of a planar graph. Moreover, we show that a planar graph G has no cut vertex if and only if N(Π(D(G))) = N(Π(D(G − v))) − 1 for any v ∈ V(G). Some applications relevant to quantum space time are indicated. Our results generalize and extend results in paper [1] [S.I. Nada, E.H. Hamouda, Fundamental group of dual graphs and applications to quantum space time, Chaos Soliton Fractals 42 (2009) 500-503].     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

splitting number is NP-complete

We consider two graph invariants that are used as a measure of nonplanarity: the splitting number of a graph and the size of a maximum planar subgraph. The splitting number of a graph G is the smallest integer k⩾0, such that a planar graph can be obtained from G by k splitting operations. Such operation replaces a vertex v by two nonadjacent vertices v₁ and v₂, and attaches the neighbors of v either to v₁ or to v₂. We prove that the splitting number decision problem is NP-complete when restricted to cubic graphs. We obtain as a consequence that planar subgraph remains NP-complete when restricted to cubic graphs. Note that NP-completeness for cubic graphs implies NP-completeness for graphs not containing a subdivision of K₅ as a subgraph.     

A Note on Heterochromatic C 4 in Edge-Colored Triangle-Free Graphs

Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥?9 and ${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$ for each vertex v of G, G has a heterochromatic C ₄.     

A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs

In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows.     

A note on the acyclic 3-choosability of some planar graphs

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two adjacent vertices in G receive the same color and (ii) no bicolored cycles exist in G. A list assignment of G is a function L that assigns to each vertex v∈V(G) a list L(v) of available colors. Let G be a graph and L be a list assignment of G. The graph G is acyclically L-list colorable if there exists an acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is said to be acyclically k-choosable. Borodin et al. proved that every planar graph with girth at least 7 is acyclically 3-choosable (Borodin et al., submitted for publication [4]). More recently, Borodin and Ivanova showed that every planar graph without cycles of length 4 to 11 is acyclically 3-choosable (Borodin and Ivanova, submitted for publication [7]). In this note, we connect these two results by a sequence of intermediate sufficient conditions that involve the minimum distance between 3-cycles: we prove that every planar graph with neither cycles of lengths 4 to 7 (resp. to 8, to 9, to 10) nor triangles at distance less than 7 (resp. 5, 3, 2) is acyclically 3-choosable.     

Extremal perfect graphs for a bound on the domination number

We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.     

Factor-critical property in 3-dominating-critical graphs

A vertex subset S of a graph G is a dominating set if every vertex of G either belongs to S or is adjacent to a vertex of S. The cardinality of a smallest dominating set is called the dominating number of G and is denoted by γ(G). A graph G is said to be γ-vertex-critical if γ(G−v)<γ(G), for every vertex v in G.Let G be a 2-connected K_1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G), we show that G−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651-1658].     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

Choosability of graphs with infinite sets of forbidden differences

The notion of the list-T-coloring is a common generalization of the T-coloring and the list-coloring. Given a set of non-negative integers T, a graph G and a list-assignment L, the graph G is said to be T-colorable from the list-assignment L if there exists a coloring c such that the color c(v) of each vertex v is contained in its list L(v) and |c(u)-c(v)|∉T for any two adjacent vertices u and v. The T-choice number of a graph G is the minimum integer k such that G is T-colorable for any list-assignment L which assigns each vertex of G a list of at least k colors.We focus on list-T-colorings with infinite sets T. In particular, we show that for any fixed set T of integers, all graphs have finite T-choice number if and only if the T-choice number of K₂ is finite. For the case when the T-choice number of K₂ is finite, two upper bounds on the T-choice number of a graph G are provided: one being polynomial in the maximum degree of the graph G, and the other being polynomial in the T-choice number of K₂.