Edge and total choosability of near-outerplanar graphs.
Edge colorings and total colorings of integer distance graphs
An integer distance graph is a graph G(D) with the set Z of integers as vertex set and two vertices u,v ∈ Z are adjacent if and only if |u-v| ∈ D where the distance set D is a subset of the positive integers N. In this note we determine the chromatic index, the choice index, the total chromatic number and the total choice number of all integer distance graphs, and the choice number of special integer distance graphs.
Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles
Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method...
Edge-coloring and -coloring for various classes of graphs.
Edge-colouring of graphs and hereditary graph properties
Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph , a hereditary graph property and we define to be the minimum number of colours needed to properly colour the edges of , such that any subgraph of induced by edges coloured by (at most) colours is in . We present a necessary and sufficient condition for the existence of . We focus on edge-colourings of graphs with respect to the hereditary properties...
Edge-Colourings of Permutation Graphs
Edge-disjoint odd cycles in graphs with small chromatic number
For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.
Edge-domatic numbers of cacti
The edge-domatic number of a graph is the maximum number of classes of a partition of its edge set into dominating sets. This number is studied for cacti, i.e. graphs in which each edge belongs to at most one circuit.
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.
Eine Färbungstheorie für endliche Graphen.
Eine Verallgemeinerung der Färbungszahlen.
Eine Verallgemeinerung der Färbungszahlen. II.
Embedding -quasistars into -cubes
Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)
Let be the family of all 2-connected plane triangulations with vertices of degree three or six. Grünbaum and Motzkin proved (in dual terms) that every graph P ∈ has a decomposition into factors P₀, P₁, P₂ (indexed by elements of the cyclic group Q = 0,1,2) such that every factor consists of two induced paths of the same length M(q), and K(q) - 1 induced cycles of the same length 2M(q). For q ∈ Q, we define an integer S⁺(q) such that the vector (K(q),M(q),S⁺(q)) determines the graph P (if P is...
Equitable colorations of graphs
Equitable coloring of Kneser graphs
The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k) are...
Equitable coloring on total graph of bigraphs and central graph of cycles and paths.
Equivalent classes for K₃-gluings of wheels
In this paper, the chromaticity of K₃-gluings of two wheels is studied. For each even integer n ≥ 6 and each odd integer 3 ≤ q ≤ [n/2] all K₃-gluings of wheels and create an χ-equivalent class.
Erdős regular graphs of even degree
In 1960, Dirac put forward the conjecture that r-connected 4-critical graphs exist for every r ≥ 3. In 1989, Erdös conjectured that for every r ≥ 3 there exist r-regular 4-critical graphs. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.
Errata: Correction of my paper 'On a problem in map colouring'