# Graphs and Combinatorics

Graphs and Combinatorics > 2017 > 33 > 4 > 991-998

Graphs and Combinatorics > 2017 > 33 > 4 > 729-734

*G*be a connected graph of chromatic number

*k*. For a

*k*-coloring

*f*of

*G*, a full

*f*-rainbow path is a path of order

*k*in

*G*whose vertices are all colored differently by

*f*. We show that

*G*has a

*k*-coloring

*f*such that every vertex of

*G*lies on a full

*f*-rainbow path, which provides a positive answer to a question posed by Lin (Simple proofs of results on paths representing all colors in proper vertex-colorings,...

Graphs and Combinatorics > 2017 > 33 > 4 > 789-799

*d*. We show that if $$d_n\ge 1$$ d n ≥ 1 , then $$\chi _{\min }(d)\le \max \left\{ 3,d_1-\frac{n+1}{4d_1}+4\right\}...

Graphs and Combinatorics > 2017 > 33 > 4 > 583-594

*G*is locally $$\mathcal {P}$$ P if for each $$v \in V(G)$$ v ∈ V ( G ) , the subgraph induced by the open neighbourhood of

*v*has property $$\mathcal P$$ P . A closed locally $$\mathcal {P}$$ P graph is defined analogously in terms of closed neighbourhoods. It is known that connected locally hamiltonian...

Graphs and Combinatorics > 2017 > 33 > 4 > 1037-1053

*G*is called the ID code number of

*G*and is denoted $$\gamma ^\mathrm{ID}(G)$$ γ ID ( G ) . In this paper, we give upper and lower bounds for...

Graphs and Combinatorics > 2017 > 33 > 4 > 1009-1022

*bull*and any set of induced subgraphs each on at most 5 vertices.

Graphs and Combinatorics > 2017 > 33 > 4 > 929-944

Graphs and Combinatorics > 2017 > 33 > 4 > 1023-1035

*G*is an assignment of the vertices of

*G*to geometric objects such that vertices are adjacent if and only if their corresponding objects are “visible” each other, that is, there is an uninterrupted channel, usually axis-aligned, between them. Depending on the objects and definition of visibility used, not all graphs are visibility graphs. In such situations, one...

Graphs and Combinatorics > 2017 > 33 > 4 > 595-615

*G*be a graph whose each component has order at least 3. Let $$s : E(G) \rightarrow {\mathbb {Z}}_k$$ s : E ( G ) → Z k for some integer $$k\ge 2$$ k ≥ 2 be an improper edge coloring of

*G*(where adjacent edges may be assigned the same color). If the induced vertex coloring $$c : V (G) \rightarrow {\mathbb {Z}}_k$$ c : V ( G ) → Z k defined by $$c(v)...

Graphs and Combinatorics > 2017 > 33 > 4 > 999-1008

*G*is called

*a rainbow tree*if no two edges of it are assigned the same color. For a vertex subset $$S\subseteq V(G)$$ S ⊆ V ( G ) , a tree is called an

*S*-

*tree*if it connects

*S*in

*G*. A

*k*-

*rainbow coloring*of

*G*is an edge-coloring of

*G*having the property that for every set

*S*of

*k*vertices of

*G*, there exists a rainbow

*S*-tree in

*G*. The minimum number...

Graphs and Combinatorics > 2017 > 33 > 4 > 945-953

*G*is

*equitable*if, for each vertex

*v*of

*G*, the number of edges of any one color incident with

*v*differs from the number of edges of any other color incident with

*v*by at most one. In the paper, we prove that every 1-planar graph has an equitable edge-coloring with

*k*colors for any integer $$k\ge 21$$ k ≥ 21 , and every planar graph has an equitable edge-coloring...

Graphs and Combinatorics > 2017 > 33 > 4 > 981-990

*V*be a finite set of points in the plane, not all on one line, and let

*l*be a line that contains at least 2 points of

*V*. We say that

*l*is a

*k*

*-bisector*of

*V*if there are at least

*k*points of

*V*on each one of the two open half-planes bounded by

*l*. For $$k \ge 6$$ k ≥ 6 we construct planar sets of $$2k+4$$ 2 k + 4 points having no

*k*-bisector (this might be best possible). Furthermore,...

Graphs and Combinatorics > 2017 > 33 > 4 > 673-687

*k*such that there exists a collection of three

*KTS*(

*v*) pairwise intersecting in the same set of

*k*blocks. In this paper for sufficiently large

*v*where $$v\equiv 3$$ v ≡ 3 (mod 6), we determine the set $$J^{3}_{R}(v)$$ J R 3 ( v ) except possibly for two values $$t_v-10$$ t v - 10 and...

Graphs and Combinatorics > 2017 > 33 > 4 > 1081-1087

Graphs and Combinatorics > 2017 > 33 > 4 > 1065-1079

*G*and

*H*, the bipartite rainbow Ramsey number

*BRR*(

*G*;

*H*) is the minimum integer

*N*such that any edge-coloring of $$K_{N,N}$$ K N , N with any number of colors contains either a monochromatic copy of

*G*or a rainbow copy of

*H*. It is known that

*BRR*(

*G*;

*H*) exists if and only if

*G*is a star or

*H*is a forest consisting of stars. For fixed $$t\ge 3$$ t ≥ 3 , ...

Graphs and Combinatorics > 2017 > 33 > 4 > 653-664

Graphs and Combinatorics > 2017 > 33 > 4 > 845-858

*k*,

*n*, a de Bruijn sequence

*B*(

*k*,

*n*) is a finite sequence of elements drawn from

*k*characters whose subwords of length

*n*are exactly the $$k^n$$ k n words of length

*n*on

*k*characters. This paper studies the unoriented de Bruijn sequence

*uB*(

*k*,

*n*), an analog to de Bruijn sequences, but for which the sequence is read both forwards and backwards to determine the set of subwords...

Graphs and Combinatorics > 2017 > 33 > 4 > 665-672

*k*-dominating graph $$D_k(G)$$ D k ( G ) of a graph

*G*is defined on the vertex set consisting of dominating sets of

*G*with cardinality at most

*k*, two such sets being adjacent if they differ by either adding or deleting a single vertex. A graph is a dominating graph if it is isomorphic to $$D_k(G)$$ D k ( G ) for some graph

*G*and some positive integer

*k*. Answering a...

Graphs and Combinatorics > 2017 > 33 > 4 > 1055-1063

Graphs and Combinatorics > 2017 > 33 > 4 > 635-652

*x*,

*y*in $$\mathbb {Z}_g^n$$ Z g n are

*qualitatively independent*if for all pairs $$(a,b)\in \mathbb {Z}_g\times \mathbb {Z}_g$$ ( a , b ) ∈ Z g × Z g , there exists $$i\in \{1,2,\ldots ,n\}$$ i ∈ { 1 , 2 , … , n } such that $$(x_i,y_i)=(a,b)$$ ( x i , y i ) = ( a , b ) . A covering array on a graph

*G*, denoted by

*CA*(

*n*,

*G*,

*g*), is a...