Special Representations for n-Bridge Links.
Special Subdivisions of K4 and 4-Chromatic Graphs.
Spectrally arbitrary complex sign pattern matrices.
Star coloring high girth planar graphs.
Star Coloring of Subcubic Graphs
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 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.
Stationary map coloring
We consider a planar Poisson process and its associated Voronoi map. We show that there is a proper coloring with 6 colors of the map which is a deterministic isometry-equivariant function of the Poisson process. As part of the proof we show that the 6-core of the corresponding Delaunay triangulation is empty. Generalizations, extensions and some open questions are discussed.
Strong Chromatic Index Of Planar Graphs With Large Girth
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
Strong products of ?-critial graphs.
Strong products of ?-critical graphs. (Summary).
Sufficient conditions for planar graphs to be 2-distance ()-colourable.
Sufficient conditions for the minimum 2-distance colorability of plane graphs of girth 6.
Sum list coloring arrays.
Sum List Edge Colorings of Graphs
Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f) over all edge...
-preserving homomorphisms of oriented graphs
A homomorphism of an oriented graph to an oriented graph is a mapping from to such that is an arc in whenever is an arc in . A homomorphism of to is said to be -preserving for some oriented graph if for every connected subgraph of isomorphic to a subgraph of , is isomorphic to its homomorphic image in . The -preserving oriented chromatic number of an oriented graph is the minimum number of vertices in an oriented graph such that there exists a -preserving...
Teorie grafů, 1736–1963 [Book]
The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs
The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures...
The 3-Rainbow Index of a Graph
Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex subset S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G). In this paper,...
The Balanced Decomposition Number of TK4 and Series-Parallel Graphs
A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G)...
The b-chromatic number of power graphs.
The bichromaticity of a graph