Search

The odd-ballooning of a graph F is the graph obtained from F by replacing each edge in F by an odd cycle of length between 3 and q (q ≥ 3) where the new vertices of the odd cycles are all different. Given a forbidden graph H and a positive integer n, the extremal number, ex(n, H), is the maximum number of edges in a graph on n vertices that does not contain H as a subgraph. Erdös et al. and Hou et al. determined the extremal number of odd-ballooning of stars. Liu and Glebov determined the extremal number of odd-ballooning of paths and cycles respectively when replacing each edge of the paths or the cycles by a triangle. In this paper we determine the extremal number and find the extremal graphs for odd-ballooning of paths and cycles, when replacing each edge of the paths or the cycles by an odd cycle of length between 3 and q (q ≥ 3) and n is sufficiently large. [ABSTRACT FROM AUTHOR]

An edge e of a graph G is called singular if it is not on a triangle; otherwise, e is nonsingular. A vertex is called singular if it is adjacent to a singular edge; otherwise, it is called nonsingular. We prove the following. Let G be a connected claw-free graph such that every locally disconnected vertex x ∈ V(G) satisfies the following conditions: (i) if x is nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 4 nonsingular edges, (ii) if x is not nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 3 nonsingular edges, (iii) if x is of degree 2, then x is singular and x is on an induced cycle C of length at least 4 with at most 2 nonsingular edges such that G [ V (C) ∩ V 2 (G) ] is a path or a cycle. Then G is either hamiltonian, or G is the line graph of the graph obtained from K 2 , 3 by attaching a pendant edge to its each vertex of degree two. Some results on forbidden subgraph conditions for hamiltonicity in 3-connected claw-free graphs are also obtained as immediate corollaries [ABSTRACT FROM AUTHOR]

We present a simple transformation for the inversion number and major index statistics on the labelings of a rooted tree with n vertices in the form of a rake with k teeth. The special case k=0 provides a simple transformation for the Mahonian statistics on the set Sn of permutations of {1,2,⋯,n}. We also extend the transformation to a bijective interpretation of the fact that the major index of the equivalence classes of the labelings is equidistributed with the major index of the permutations in Sn satisfying the condition that the elements 1,2,⋯,k appear in increasing order. [ABSTRACT FROM AUTHOR]

It is one of fundamental theorems in graph theory that every even graph has a circuit decomposition. This classical result for ordinary graphs is extended in this paper for uniform bridgeless hypergraphs if the degree of every vertex is even. One of major open problems for shortest circuit cover was a conjecture proposed by Itai and Rodeh (Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 62, pp. 289-299. Springer, Berlin, 1978) that every bridgeless graph G has a circuit cover of total length at most |E|+|V|-1. This conjecture was solved by Fan (J Combin Theory Ser B 74:353-367, 1998) for ordinary graphs, and is extended in this paper for bridgeless hypergraphs. [ABSTRACT FROM AUTHOR]

Let colg(G) be the game coloring number of a given graph G. Define the game coloring number of a family of graphs H as colg(H):=max{colg(G):G∈H}. Let Pk be the family of planar graphs of girth at least k. We show that colg(P7)≤5. This result extends a result about the game coloring number by Wang and Zhang [10] (colg(P8)≤5). We also show that these bounds are sharp by constructing a graph G where G∈Pk for each k≤8 such that colg(G)=5. As a consequence, colg(Pk)=5 for k=7,8. [ABSTRACT FROM AUTHOR]

In this paper, we explore minimal k-connected non-Hamiltonian graphs. Graphs are said to be minimal in the context of some containment relation; we focus on subgraphs, induced subgraphs, minors, and induced minors. When k=2, we discuss all minimal 2-connected non-Hamiltonian graphs for each of these four relations. When k=3, we conjecture a set of minimal non-Hamiltonian graphs for the minor relation and we prove one case of this conjecture. In particular, we prove all 3-connected planar triangulations which do not contain the Herschel graph as a minor are Hamiltonian. [ABSTRACT FROM AUTHOR]

Let Z be the set of integers and Zl be the set of integers modulo l. A set L⊆T=Zl1×Zl2×⋯×Zlm is called a line if there exist a,b∈T such that L={a+tb∈T:t∈Z}. A set X⊆T is called a no-three-in-line set if |X∩L|≤2 for all the lines L in T. The maximum size of a no-three-in-line set is denoted by τT. Let m≥2 and k1,k2,…,km be positive integers such that gcd(ki,kj)=1 for all i, j with i≠j. In this paper, we will show that τZk1n×Zk2n×⋯×Zkmn≤2nm-1.We will give sufficient conditions for which the equality holds. When k1=k2=⋯=km=1 and n=pl where p is a prime and l≥1 is an integer, we will show that equality holds if and only if p=2 and l=1, i.e., τZpl×Zpl×⋯×Zpl=2pl(m-1) if and only if p=2 and l=1. [ABSTRACT FROM AUTHOR]

An edge colouring of a graph G is complete if for any distinct colours c1 and c2 one can find in G adjacent edges coloured with c1 and c2, respectively. The pseudoachromatic index of G is the maximum number of colours in a complete edge colouring of G. Let ψ(n) denote the pseudoachromatic index of Kn. In the paper we proved that if x≥2 is an integer and n∈{4x2-x,⋯,4x2+3x-3}, then ψ(n)≤2x(n-x-1). Let q be an even integer and let ma=(q+1)2-a. If there is a projective plane of order q, a complete edge colouring of Kma with (ma-a)q colours, a∈{-1,0,⋯,q2+1}, is presented. The main result states that if q≥4 is an integer power of 2, then ψ(ma)=(ma-a)q for any a∈{-1,0,⋯,1+4q+92-1}. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad-Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs. [ABSTRACT FROM AUTHOR]

Let λKv be the complete graph on v vertices in which each pair of vertices is joined by exactly λ edges. An m-cycle system of λKv is a collection C of cycles of length m whose edges partition the edges of λKv. An m-cycle system C of λKv is said to be resolvable if the m-cycles in C can be partitioned into parallel classes R={R1,R2,…,Rλ(v-1)/2} and C is denoted by (v,m,λ)-RCS, R is called a resolution. If a (v,m,λ)-RCS has a pair of orthogonal resolutions, it is said to be doubly resolvable and is denoted by (v,m,λ)-DRCS. In this paper, applying direct constructions and recursive constructions, we show that a (v, 4, 2)-DRCS exists if and only if v≡0(mod4). [ABSTRACT FROM AUTHOR]

In this paper, we survey results and conjectures on degree conditions for the existence of vertex-disjoint cycles and paths. In particular, we focus on the type of degree conditions, the type of cycles or paths, and relations between results or conjectures. [ABSTRACT FROM AUTHOR]

The class of 2K2-free graphs and its various subclasses have been studied in a variety of contexts. In this paper, we are concerned with the colouring of (P3∪P2)-free graphs, a super class of 2K2-free graphs. We derive a O(ω3) upper bound for the chromatic number of (P3∪P2)-free graphs, and sharper bounds for (P3∪P2, diamond)-free graphs and for (2K2, diamond)-free graphs, where ω denotes the clique number. The last two classes are perfect if ω≥5 and ≥4 respectively. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be an isolate-free graph. For some α with 0<α≤1, a subset S of V is said to be an α-dominating set if for all v∈V\S,|N(v)∩S|≥α|N(v)|. The size of a smallest such S is called the α-domination number and is denoted by γα(G). A set S⊆V is said to be an α-rate dominating set of G if for any vertex v∈V, |N[v]∩X|≥α|N(v)|. The minimum cardinality of an α-rate dominating set of G is called the α-rate domination numberγ×α(G). The set of distinct values of γα(G) as α runs over (0, 1] is called the α-domination spectrum of a graph G, i.e., Spα(G)={γα(G):α∈(0,1]}. In this paper, we study some properties of Spα(G) and show that γα(G) changes its value only at rational points as α runs over (0, 1]. Using this result, we characterize some values of α such that γα(G)≤nα, where n is the number of vertices in G, holds. Finally, we present some improved probabilistic upper bounds of α-domination number and α-rate domination number of a graph G. [ABSTRACT FROM AUTHOR]

The (n, k)-star graphs are an important class of interconnection networks that generalize star graphs, which are superior to hypercubes. In this paper, we continue the work begun by Cheng et al. (Graphs Combin 33(1):85–102, 2017) and complete the classification of all the (n, k)-star graphs that are Cayley. [ABSTRACT FROM AUTHOR]

Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover Q and a stable set cover S s.t. every clique in Q intersects every stable set in S. Normal graphs can be considered as closure of perfect graphs by means of co-normal products and graph entropy. Perfect graphs have been characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al.). Körner and de Simone observed that C5, C7, and C¯7 are minimal not normal and conjectured, in analogy to the Strong Perfect Graph Theorem, that every (C5,C7,C¯7)-free graph is normal (Normal Graph Conjecture, Körner and de Simone). Recently, this conjecture has been disproved by Harutyunyan, Pastor and Thomassé. However, in this paper we verify it for two classes of sparse graphs, 1-trees and cacti. In addition, we provide both linear time recognition algorithms and characterizations for the normal graphs within these two classes. [ABSTRACT FROM AUTHOR]

Let G=H[G1,G2,…,Gk] be the generalized join graph ofG1,G2,…,Gk determined by H. In this paper, we give a decomposition formula for the Bartholdi zeta function of G. As applications, we obtain explicit formulae for Bartholdi zeta functions of some special kinds of graphs, such as the complete multipartite graph, the wheel, etc. [ABSTRACT FROM AUTHOR]

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, γ(G), and total domination number, γt(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, Γ(G), and the upper total domination number, Γt(G), are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that γt(G)/γ(G)≤2 and Γt(G)/Γ(G)≤2 for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying γt(G)/γ(G)=2, and we characterize the connected cubic graphs G satisfying Γt(G)/Γ(G)=2. [ABSTRACT FROM AUTHOR]

Let S={n1,n2,…,ns}, s≥2, be a set of positive integers. A mixed hypergraph H=(X,C,D) is a one-realization of S if for every i∈S, there exists a unique coloring (up to permutations of the colors) using precisely i colors and there are no other colorings.For any r≥3 and set of integers S, we show that any r-uniform one-realization of S is isomorphic to a subhypergraph of Hn1,…,ns2 which is a special r-uniform one-realization of S. [ABSTRACT FROM AUTHOR]

A t-tone k-coloring of a graph G=(V,E) is a function f:V→[k]t such that |f(u)∩f(v)| for all distinct vertices u and v. The t-tone chromatic number of G, denoted τt(G), is the smallest positive integer k such that G has a t-tone k-coloring. The Wiener index W(G) of a connected graph G is the sum of the distances of all pairs of vertices of G. In this paper, we prove that τt(G)≥t|V|-W(G)+|V|2 for a connected graph G and obtain a characterization when the equality holds. As a result, for each graph G (not necessarily connected), we obtain a formula for the t-tone chromatic number of G when t is sufficiently large. [ABSTRACT FROM AUTHOR]

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on four vertices (not necessarily induced) is bi-colored. The star chromatic number of G, denoted by χs(G), is the minimum number of colors needed to star color G. Similar to the notion of χ-boundedness in graphs, we say that a hereditary class of graphs G is χs-bounded if, for some integer valued function f, χs(G)≤f(ω(G)) for every G∈G, where ω(G) is the maximum number of vertices that are pairwise adjacent in G. We show that some classes of perfect graphs, some classes of (P5,C4)-free graphs, and some classes of K1,3-free graphs are χs-bounded. We also give examples in most of the cases to show that the bounds are tight. [ABSTRACT FROM AUTHOR]

Studies of the p-ary codes from the adjacency matrices of uniform subset graphs Γ(n,k,r) and their reflexive associates have shown that a particular family of codes defined on the subsets are intimately related to the codes from these graphs. We describe these codes here and examine their relation to some particular classes of uniform subset graphs. In particular we include a complete analysis of the p-ary codes from Γ(n,3,r) for p≥5, thus extending earlier results for p=2,3. [ABSTRACT FROM AUTHOR]

Given a graph H, we say a graph G is H-saturated if G does not contain H as a subgraph and the addition of any edge e′∉E(G) results in H as a subgraph. In this paper, we construct (K4-e)-saturated graphs with |E(G)| either the size of a complete bipartite graph, a 3-partite graph, or in the interval 2n-4,n2n2-n+6. We then extend the (K4-e)-saturated graphs to (Kt-e)-saturated graphs. [ABSTRACT FROM AUTHOR]

Back in 1922, Franklin proved that every 3-polytope $$P_5$$ with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol' and Madaras (Discuss Math Graph Theory 16:207-217, 1996) ensured a 4-path with the degree sum at most 23. A path $$v_1\ldots v_k$$ is a $$(d_1,\ldots d_k)$$ -path if $$d(v_i)\le d_i$$ whenever $$1\le i\le k$$ . Recently, Borodin and Ivanova proved that every $$P_5$$ has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, and Ivanova proved the existence of a (5, 6, 6, 6)-path or (5, 5, 5, 7)-path, where both descriptions are tight. The purpose of our paper is to give all tight descriptions of 4-paths in $$P_5$$ s. [ABSTRACT FROM AUTHOR]

A cycle C in a graph G is dominating if every edge of G is incident with at least one vertex of C. For a set $$\mathcal {H}$$ of connected graphs, a graph G is said to be $$\mathcal {H}$$ -free if G does not contain any member of $$\mathcal {H}$$ as an induced subgraph. When $$|\mathcal {H}| = 2, \mathcal {H}$$ is called a forbidden pair. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every 2-connected $$\{P_{5}, K_{4}^{-}\}$$ -free graph contains a longest cycle which is a dominating cycle. (ii) Every 2-connected $$\{P_{5}, W^{*}\}$$ -free graph contains a longest cycle which is a dominating cycle. Here $$P_{5}$$ is the path of order $$5, K_{4}^{-}$$ is the graph obtained from the complete graph of order 4 by removing one edge, and $$W^{*}$$ is the graph obtained from two triangles and an edge by identifying one vertex in each. [ABSTRACT FROM AUTHOR]

Ruskey and Savage asked the following question: does every matching of a hypercube $$Q_{n}$$ for $$n\ge 2$$ extend to a Hamiltonian cycle of $$Q_{n}$$ ? Fink confirmed that the question is true for every perfect matching, thus solved Kreweras' conjecture. In this paper we prove that every matching of at most $$3n-10$$ edges can be extended to a Hamiltonian cycle of $$Q_{n}$$ for $$n\ge 4$$ . [ABSTRACT FROM AUTHOR]

We call an edge colouring of a graph $$G$$ a rainbow colouring if every pair of vertices is joined by a rainbow path, i.e., a path where no two edges have the same colour. The minimum number of colours required for a rainbow colouring of the edges of $$G$$ is called the rainbow connection number (or rainbow connectivity) $${\mathrm {rc}}(G)$$ of $$G$$ . We investigate sharp thresholds in the Erdős-Rényi random graph for the property ' $${\mathrm {rc}}(G)\le r$$ ' where $$r$$ is a fixed integer. It is known that for $$r=2$$ , rainbow connection number $$2$$ and diameter $$2$$ happen essentially at the same time in random graphs. For $$r \ge 3$$ , we conjecture that this is not the case, propose an alternative threshold, and prove that this is an upper bound for the threshold for rainbow connection number $$r$$ . [ABSTRACT FROM AUTHOR]

Let $$P_{k}$$ and $$C_k$$ respectively denote a path and a cycle on $$k$$ vertices. In this paper we give necessary and sufficient conditions for the existence of $$\{P_{5}, C_4\}_{\{p, q\}}$$ -decomposition of tensor product and cartesian product of complete graphs. Further we extent such decomposition to complete multipartite graphs. [ABSTRACT FROM AUTHOR]

We construct face two-colourable embeddings of the complete graph $$K_{2n+1}$$ in which every face is a cycle of length $$n$$ ; equivalently biembeddings of pairs of symmetric $$n$$ -cycle systems. We prove that the necessary and sufficient condition for the existence of such an embedding in an orientable surface is for $$n\ge 3$$ to be odd, and in a nonorientable is for $$n\ge 4$$ . [ABSTRACT FROM AUTHOR]

If $$G$$ is a claw-free Hamiltonian graph of order $$n$$ and maximum degree $$\Delta $$ with $$\Delta \ge 24$$ , then $$G$$ has cycles of at least $$\min \left\{ n,\left\lceil \frac{3}{2}\Delta \right\rceil \right\} -2$$ many different lengths. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a $$k$$ -connected graph with $$k\ge 2$$ . In this paper we first prove that: For two distinct vertices $$x$$ and $$z$$ in $$G$$ , it contains a path connecting $$x$$ and $$z$$ which passes through its any $$k-2$$ specified vertices with length at least the average degree of the vertices other than $$x$$ and $$z$$ . Further, with this result, we prove that: If $$G$$ has $$n$$ vertices and $$m$$ edges, then it contains a cycle of length at least $$2m/(n-1)$$ passing through its any $$k-1$$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition. [ABSTRACT FROM AUTHOR]

In this paper we investigate the structures of short cycles in a weighted graph. By Thomassen's $$3$$ -path-condition theory (Thomassen in J Comb Theory Ser 48:155-177, ), it is easy to find a shortest cycle in a collection of cycles beyond a subspace of the cycle space of a graph. What is more difficult for one to do is to find a shortest cycle within a subspace of the cycle space in polynomial time. By using the Dijkstra's algorithm (Dijkstra in Numer Math 1:55-61, ) we find a collection $$\mathcal {C}$$ of cycles containing many types of short cycles within a given subspace of the cycle space of a graph and this implies a polynomial time algorithm (called extended fundamental cycle algorithm) to locate all the possible shortest cycles in a weighted graph. In the case of unweighted graphs, the algorithm may also find every shortest even cycle in a graph, this greatly improved a result of Grötschel and Pulleyblank (Oper Res Lett 1:23-27, ), Monien (Computing 31:355-369, ), Yuster and Zwick (SIAM J Discrete Math 10:209-222, ). In fact, our algorithm shows that there are at most $$O(n^4)$$ many such short cycles in an unweighted graph of order $$n$$ . Further more, our fundamental cycle method may find a minimum cycle base (or simply MCB as some scholars named) in the cycle space of a graph. Since the structure of MCB's is unique (Ren and Deng in Discrete Math 307:2654-2660, ), this shows that, in the sense, cycles in a MCB are nearly-fundamental (i.e., each element in a MCB is a sum of at most two fundamental cycles). This provides a new way to study MCB. [ABSTRACT FROM AUTHOR]

In this paper we obtain an intermediate value theorem for the decycling numbers of Toeplitz graphs: if $$n \ge 3$$ , and $$0 \le r \le n - 2$$ , then there exists a Toeplitz graph of order $$n$$ with decycling number $$r$$ . We also prove that the decycling numbers of connected Cayley graphs of order $$n$$ satisfy the intermediate value property if and only if $$n = 4$$ or $$6$$ . [ABSTRACT FROM AUTHOR]

For an integer $$\ell $$ at least three, we prove that every Hamiltonian $$P_\ell $$ -free graph $$G$$ on $$n>\ell $$ vertices has cycles of at least $$\frac{2}{\ell }n-1$$ different lengths. For small values of $$\ell $$ , we can improve the bound as follows. If $$4\le \ell \le 7$$ , then $$G$$ has cycles of at least $$\frac{1}{2}n-1$$ different lengths, and if $$\ell $$ is $$4$$ or $$5$$ and $$n$$ is odd, then $$G$$ has cycles of at least $$n-\ell +2$$ different lengths. [ABSTRACT FROM AUTHOR]

Let $$D=(V(D), A(D))$$ be a digraph, $$DP(D)$$ be the set of directed paths of $$D$$ and let $$\varPi $$ be a subset of $$DP(D)$$ . A subset $$S\subseteq V(D)$$ will be called $$\varPi $$ -independent if for any pair $$\{x, y\} \subseteq S$$ , there is no $$xy$$ -path nor $$yx$$ -path in $$\varPi $$ ; and will be called $$\varPi $$ -absorbing if for every $$x\in V(D)\setminus S$$ there is $$y\in S$$ such that there is an $$xy$$ -path in $$\varPi $$ . A set $$S\subseteq V(D)$$ will be called a $$\varPi $$ -kernel if $$S$$ is $$\varPi $$ -independent and $$\varPi $$ -absorbing. This concept generalize several 'kernel notions' like kernel or kernel by monochromatic paths, among others. In this paper we present some sufficient conditions for the existence of $$\varPi $$ -kernels. [ABSTRACT FROM AUTHOR]

For given graphs $$G_1, G_2, \ldots , G_t$$ , the multicolor Ramsey number $$R(G_1, G_2, \ldots , G_t)$$ is the smallest positive integer $$n$$ , such that if the edges of the complete graph $$K_n$$ are partitioned into $$t$$ disjoint color classes giving $$t$$ graphs $$H_1,H_2,\ldots ,H_t$$ , then at least one $$H_i$$ has a subgraph isomorphic to $$G_i$$ . In this paper, we show that if $$(n,m)\ne (3,3), (3,4)$$ and $$m\ge n$$ , then $$R(P_3,P_n,P_m)=R(P_n,P_m)=m+\lfloor \frac{n}{2}\rfloor -1$$ . Consequently, $$R(P_3,mK_2,nK_2)=2m+n-1$$ for $$m\ge n\ge 3$$ . [ABSTRACT FROM AUTHOR]

In this paper, we characterize connected $$\{K_{1,3},N(2,1,0)\}$$ -free but not $$N(1,1,1)$$ -free graphs. By combining our result and a theorem showed by Duffus et al. (every $$2$$ -connected $$\{K_{1,3},N(1,1,1)\}$$ -free graph is Hamiltonian), we give an alternative proof of Bedrossian's theorem (every $$2$$ -connected $$\{K_{1,3},N(2,1,0)\}$$ -free graph is Hamiltonian). [ABSTRACT FROM AUTHOR]

For an integer $$k$$ with $$k \ge 2$$ , a $$k$$ - tree (resp. a $$k$$ - forest) is a tree (resp. forest) with maximum degree at most $$k$$ . In this paper, we show that for any integer $$k$$ with $$k \ge 3$$ , any connected $$K_{1,k+1}$$ -free graph has a spanning $$k$$ -tree or a spanning $$k$$ -forest with only large components. [ABSTRACT FROM AUTHOR]

A structure is called ultrahomogeneous if every isomorphism between finitely generated substructures of the structure extends to an automorphism of the structure. Recently, Cameron and Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely generated substructures of the structure extends to an endomorphism of the structure. In this paper we classify finite homomorphism-homogeneous oriented graphs with loops allowed which are uniform (that is, either all vertices have a loop or no vertex has a loop) or disconnected. [ABSTRACT FROM AUTHOR]

A graph is $$d$$ -improperly chromatic-choosable if its $$d$$ -improper choice number coincides with its $$d$$ -improper chromatic number. For fixed $$d\ge 0$$ , we show that if the $$d$$ -improper chromatic number is close enough to $$\frac{1}{d+1}$$ of the number of vertices in $$G$$ , then $$G$$ is $$d$$ -improperly chromatic-choosable. As a consequence, we show that the join $$G + K_n$$ is $$d$$ -improperly chromatic-choosable when $$n\ge (|V(G)|+d)^2$$ . We also raise a conjecture on $$d$$ -improper chromatic-choosability. [ABSTRACT FROM AUTHOR]

Unlike graphs, digraphs or binary relational structures, the 2-structures do not define precise links between vertices. They only yield an equivalence between links. Also 2-structures provide a suitable generalization in the framework of clan decomposition. Let $$\sigma $$ be a 2-structure. A subset $$C$$ of $$V(\sigma )$$ is a clan of $$\sigma $$ if for each $$v\in V(\sigma ){\setminus }C$$ , $$v$$ is linked in the same way to all the elements of $$C$$ . A 2-structure $$\sigma $$ is clan primitive if $$|V(\sigma )|\ge 3$$ and all its clans are trivial. A clan primitive 2-structure $$\sigma $$ is critically primitive if $$\sigma [V(\sigma ){\setminus }\{v\}]$$ is not primitive for every $$v\in V(\sigma )$$ . A clan of cardinality 2 is a twin pair. A 2-structure $$\sigma $$ is twin primitive if $$|V(\sigma )|\ge 3$$ and $$\sigma $$ has no twin pairs. A twin primitive 2-structure $$\sigma $$ is critically twin primitive if $$\sigma [V(\sigma ){\setminus }\{v\}]$$ is not twin primitive for every $$v\in V(\sigma )$$ . First, a twin decomposition is provided for 2-structures. Second, twin primitivity is studied by proving analogues of results on clan primitivity. Third, the notion of critically closed subset is introduced to characterize critically twin primitive 2-structures. [ABSTRACT FROM AUTHOR]

In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite digraphs $${\mathcal D}K_{m, n}$$ and complete digraphs $${\mathcal D}K_n$$ into directed paths $${\mathop {P}\limits ^{\rightarrow }}_{k+1}$$ and directed cycles $${\mathop {C}\limits ^{\rightarrow }}_{k}$$ with $$k$$ arcs each. In particular, we prove that: (1) For any nonnegative integers $$p$$ and $$q$$ ; and any positive integers $$m$$ , $$n$$ , and $$k$$ with $$m\ge k$$ and $$n\ge k$$ ; a decomposition of $${\mathcal D} K_{m, n}$$ into $$p$$ copies of $${\mathop {P}\limits ^{\rightarrow }}_{k+1}$$ and $$q$$ copies of $${\mathop {C}\limits ^{\rightarrow }}_{k}$$ exists if and only if $$k(p+q)=2mn$$ , $$p\ne 1$$ , $$(m, n, k, p)\ne (2, 2, 2, 3)$$ , and $$k$$ is even when $$q>0$$ . (2) For any nonnegative integers $$p$$ and $$q$$ and any positive integers $$n$$ and $$k$$ with $$k$$ even and $$n\ge 2k$$ , a decomposition of $${\mathcal D} K_{n}$$ into $$p$$ copies of $${\mathop {P}\limits ^{\rightarrow }}_{k+1}$$ and $$q$$ copies of $${\mathop {C}\limits ^{\rightarrow }}_{k}$$ exists if and only if $$k(p+q)=n(n-1)$$ and $$p\ne 1$$ . We also give necessary and sufficient conditions for such decompositions to exist when $$k=2$$ or $$4$$ . [ABSTRACT FROM AUTHOR]

A result of Haxell (Graphs Comb 11:245-248, ) is that if $$G$$ is a graph of maximal degree $$\Delta $$ , and its vertex set is partitioned into sets $$V_i$$ of size $$2\Delta $$ , then there exists an independent system of representatives (ISR), namely an independent set in the graph consisting of one vertex from each $$V_i$$ . Aharoni and Berger (Trans Am Math Soc 358:4895-4917, ) generalized this result to matroids: if a matroid $$\mathcal {M}$$ and a graph $$G$$ with maximal degree $$\Delta $$ share the same vertex set, and if there exist $$2\Delta $$ disjoint bases of $$\mathcal {M}$$ , then there exists a base of $$\mathcal {M}$$ that is independent in $$G$$ . In the Haxell result the matroid is a partition matroid. In that case, a well known conjecture, the strong coloring conjecture, is that in fact there is a partition into ISRs. This conjecture extends to the matroidal case: under the conditions above there exist $$2\Delta (G)$$ disjoint $$G$$ -independent bases. In this paper we make a modest step: proving that for $$\Delta \ge 3$$ , under this condition there exist two disjoint $$G$$ -independent bases. The proof is topological. [ABSTRACT FROM AUTHOR]

Can a non self-complementary graph have the same chromatic polynomial as its complement? The answer to this question of Akiyama and Harrary is positive and was given by J. Xu and Z. Liu. They conjectured that every such graph has the same degree sequence as its complement. In this paper we show that there are infinitely many graphs for which this conjecture does not hold. We then solve a more general variant of the Akiyama-Harary problem by showing that there exists infinitely many non self-complementary graphs having the same Tutte polynomial as their complements. [ABSTRACT FROM AUTHOR]

Given a set $$\mathcal {F}$$ of graphs, a graph $$G$$ is $$\mathcal {F}$$ -free if $$G$$ does not contain any member of $$\mathcal {F}$$ as an induced subgraph. We say that $$\mathcal {F}$$ is a degree-sequence-forcing set if, for each graph $$G$$ in the class $$\mathcal {C}$$ of $$\mathcal {F}$$ -free graphs, every realization of the degree sequence of $$G$$ is also in $$\mathcal {C}$$ . A degree-sequence-forcing set is minimal if no proper subset is degree-sequence-forcing. We characterize the non-minimal degree-sequence-forcing sets $$\mathcal {F}$$ when $$\mathcal {F}$$ has size $$3$$ . [ABSTRACT FROM AUTHOR]

A vertex-cut $$S$$ of a connected graph $$G$$ is called a restricted vertex-cut if no vertex $$u$$ of the graph $$G$$ satisfies $$N_G(u)\subseteq S$$ . The restricted connectivity $$\kappa '(G)$$ of the graph $$G$$ is the cardinality of a minimum restricted vertex-cut of $$G$$ ; this is a more refined index than the connectivity parameter $$\kappa (G)$$ . In this paper, we prove that $$\kappa '(K_m\times G_2)=2k_2+m-2$$ , where $$G_2$$ is a $$k_2\ (\ge 2)$$ -regular and maximally connected graph with girth $$g(G_2)\ge 4$$ ; and $$\kappa '(G_1\times G_2)=2k_1+2k_2-2$$ , where $$G_i$$ is a $$k_i\ (\ge 2)$$ -regular and maximally connected graph with girth $$g(G_i)\ge 4$$ for $$1\le i\le 2$$ . Furthermore, we determine the restricted connectivity of a class of minimal Abelian Cayley graphs. [ABSTRACT FROM AUTHOR]

In online list coloring [introduced by Zhu (Electron J Comb 16(1):#R127, ) and Schauz (Electron J Comb 16:#R77, )], on each round the set of vertices having a particular color in their lists is revealed, and the coloring algorithm chooses an independent subset of this set to receive that color. For a graph $$G$$ and a function $$f:\,V(G)\rightarrow {\mathbb N}$$ , the graph is $$f$$ - paintable if there is an algorithm to produce a proper coloring when each vertex $$v$$ is allowed to be presented at most $$f(v)$$ times. The sum-paintability of $$G$$ , denoted $$\chi _{sp}(G)$$ , is $$\min \{\sum f(v):\,G$$ is $$f$$ -paintable $$\}$$ . Basic results include $$\chi _{sp}(G)\le |V(G)|+|E(G)|$$ for every graph $$G$$ and $$\chi _{sp}(G)=(\sum _{i=1}^{k} \chi _{sp}(H_i))-(k-1)$$ when $$H_{1},\ldots ,H_{k}$$ are the blocks of $$G$$ . Also, adding an ear of length $$\ell $$ to $$G$$ adds $$2\ell -1$$ to the sum-paintability, when $$\ell \ge 3$$ . Strengthening a result of Berliner et al., we prove $$\chi _{sp}(K_{2,r})=2r + \min \{l+m:\,lm>r\}$$ . The generalized theta-graph $$\Theta _{\ell _{1},\ldots ,\ell _{k}}$$ consists of two vertices joined by internally disjoint paths of lengths $$\ell _{1},\ldots ,\ell _{k}$$ . A book is a graph of the form $$\Theta _{1,2,\dots ,2}$$ , denoted $$B_r$$ when there are $$r$$ internally disjoint paths of length 2. We prove $$\chi _{sp}(B_r)=2r + \min _{l,m\in \mathbb {N}}\{l+m:\,m(l-m)+{m\atopwithdelims ()2}>r\}$$ . We use these results to determine the sum-paintability for all generalized theta-graphs. [ABSTRACT FROM AUTHOR]

The square $$G^2$$ of a graph $$G$$ is defined on the vertex set $$V(G)$$ of $$G$$ such that any two vertices with distance at most two in $$G$$ are linked by an edge. In this paper, the chromatic number and equitable chromatic number of the square $$S^2(n,k)$$ of Sierpiński graph $$S(n,k)$$ are studied. It is obtained that $$\chi (S^2(n,k))=\chi _{=}(S^2(n,k))=k+1$$ for $$n\ge 2$$ and $$k\ge 2$$ . [ABSTRACT FROM AUTHOR]

The regular number of a graph $$G$$ denoted by $$reg(G)$$ is the minimum number of subsets into which the edge set of $$G$$ can be partitioned so that the subgraph induced by each subset is regular. In this work we answer to the problem posed as an open problem in Ganesan et al. (J Discrete Math Sci Cryptogr 15(2-3):49-157, ) about the complexity of determining the regular number of graphs. We show that computation of the regular number for connected bipartite graphs is NP-hard. Furthermore, we show that, determining whether $$ reg(G) = 2 $$ for a given connected $$3$$ -colorable graph $$ G $$ is NP-complete. Also, we prove that a new variant of the Monotone Not-All-Equal 3-Sat problem is NP-complete. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph with a fixed orientation and $$A$$ an abelian group. Denote by $$F(G, A)$$ the set of all functions $$f: E(G)\rightarrow A$$ . The graph $$G$$ is $$A$$ -colorable if for any function $$f\in F(G, A)$$ , there is a map $$c: V(G)\rightarrow A$$ such that for each directed edge $$e=uv$$ from $$u$$ to $$v$$ , $$c(u)-c(v)\not = f(uv)$$ . The group chromatic number $$\chi _g(G)$$ is the minimum positive integer $$m$$ such that for any abelian group $$A$$ with $$|A|\ge m$$ , $$G$$ is $$A$$ -colorable. In this paper, we prove that for any Halin graph $$G$$ , $$\chi _g(G)\le 4$$ with equality if and only if $$G$$ is isomorphic to an odd wheel; for any Pseudo-Halin graph $$G$$ , $$\chi _g(G)\le 4$$ with equality if and only if $$G$$ contains a specified subtree. [ABSTRACT FROM AUTHOR]

A semi-coloring is a fractional-type edge coloring of graphs. Daniely and Linial (J Graph Theory 69:426-440, ) conjectured that every graph has a semi-coloring. In this paper, we give an affirmative answer to this conjecture by considering a $$2$$ -factor in almost regular graphs. [ABSTRACT FROM AUTHOR]