Search
Search Results
-
Rainbow Pancyclicity in a Collection of Graphs Under the Dirac-type Condition
Let G = { G i : i ∈ [ n ]} be a collection of not necessarily distinct n -vertex graphs with the same vertex set V , where G can be seen as an edge-colored...
-
Majority choosability of 1-planar digraph
A majority coloring of a digraph D with k colors is an assignment π : V ( D ) → {1, 2, …, k } such that for every v ∈ V ( D ) we have π ( w ) = π ( v ) for at most...
-
Rainbow and Monochromatic Vertex-connection of Random Graphs
A vertex-colored path P is rainbow if its internal vertices have distinct colors; whereas P is monochromatic if its internal vertices are colored the...
-
Incidence Coloring of Outer-1-planar Graphs
A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge....
-
The Chromatic Number of the Product of 14-Chromatic Graphs Can BE 13
We show that for any n ≥ 13, there exist graphs with chromatic number larger than n whose product has chromatic number n . Our construction is an...
-
1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on n vertices...
-
Strict Neighbor-Distinguishing Total Index of Graphs
A total-coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v , the set of colors used on u and its...
-
Partitioning a planar graph without chordal 5-cycles into two forests
It was known that the vertex set of every planar graph can be partitioned into three forests. We prove that the vertex set of a planar graph without...
-
Strong Edge Coloring of Outerplane Graphs with Independent Crossings
The strong chromatic index of a graph is the minimum number of colors needed in a proper edge coloring so that no edge is adjacent to two edges of...
-
Maximal Digraphs with Respect to Primitive Positive Constructability
We study the class of all finite directed graphs (digraphs) up to primitive positive constructibility. The resulting order has a unique maximal...
-
Acyclic Edge Coloring of 1-planar Graphs without 4-cycles
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G . The acyclic chromatic index
... -
Every Graph Embedded on the Surface with Euler Characteristic Number ε = −1 is Acyclically 11-choosable
A proper vertex coloring of a graph G is acyclic if there is no bicolored cycles in G . A graph G is acyclically k-choosable if for any list...
-
1-planar Graphs without 4-cycles or 5-cycles are 5-colorable
A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge. A proper vertex k -coloring of a...
-
2-divisibility of Some Odd Hole Free Graphs
Let G be a graph. We say that G is 2-divisible if for each induced subgraph H of G , either V ( H ) is a stable set, or V ( H ) can be partitioned into two...
-
List 2-distance Coloring of Planar Graphs with Girth Five
A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors. A list...
-
Total-coloring of Sparse Graphs with Maximum Degree 6
Given a graph G = ( V, E ) and a positive integer k , a k -total-coloring of G is a map** φ: V ⋃ E → {1, 2, ⋯, k } such that no two adjacent or incident...
-
On Decidability of Hyperbolicity
We prove that a wide range of coloring problems for graphs on surfaces can be resolved by inspecting a finite number of configurations.
-
Acyclic Choosability of Graphs with Bounded Degree
An acyclic colouring of a graph G is a proper vertex colouring such that every cycle uses at least three colours. For a list assignment L = { L ( v )∼ v ...